無源感知網絡中能耗和延遲平衡的機會路由協議?

高宏超 , 陳曉江,2 , 徐 丹,2 , 彭 瑤,2 , 湯戰勇,2 , 房鼎益,2

1(西北大學 信息科學與技術學院,陜西 西安 710127)

2(陜西省無源物聯網國際聯合研究中心(西北大學),陜西 西安 710127)

目前,感知網絡中絕大部分感知節點是有源節點,即采用電池供電[1].于是,電池能量耗盡就會導致感知網絡工作異常或者所獲信息失真.因此,節能降耗以延長感知節點乃至感知網絡的工作時間,成為一個重要的研究課題.現有的在低功耗感知元器件、低功耗處理模塊芯片、低功耗通信等方面技術的不斷發展,在很大程度上緩解了節點能量有限性問題,然而,它們無法從根本上解決感知節點能量耗竭導致節點失效以及感知網絡異常這一難題.而且在一些特殊的應用中,如在火山監測預警系統這樣的自然條件惡劣的野外環境中[2],或者軍事作戰中要監視敵方行動這樣的需求,有些待監測本體如農作物需要在24 小時全天候監控[3]等場景下,由于環境具有監測范圍大、部署區域偏遠、難以進行長時間的人力監測等特點,我們無法定期更換布置在惡劣環境或敵對環境中的感知節點的電池.因此,解決感知節點不因電池電量耗竭而停止工作,一直是需要解決的問題.

近年來,無源感知網絡研究的興起給感知網絡帶來了新的發展機遇,為解決節點電量有限問題帶來了曙光.這種網絡的主要特點是:(1) 網絡中感知節點自身不攜帶電池,節點通過能量捕獲技術將環境中的能源充分利用,來補充自己的能耗,本文中將這類節點稱為能量收集型節點,即無源節點;(2) 無源感知網絡中的感知節點具有低功耗的感知模塊、處理模塊以及低能耗通信協議,能夠完成特定的感知和數據傳輸任務.利用能量收集型節點的特性,無源感知網絡能夠獲得更長的生存周期,從而更好地完成長期監測型任務.

根據無源網絡的特點,節點可以通過能量收集技術[4],利用存在于人們周圍的可利用的能源,如光能、熱能、風能、電磁波等,周期性地為自己供電,以保證其正常工作.然而,無源節點在每一個周期內所捕獲的能量遠遠小于有源節點中電池所提供的能量,因此,如何在節點所獲能量如此小的無源網絡中降低節點能耗,以保證節點足以支撐自身順利完成數據傳輸的過程,成為亟需解決的問題.再者,網絡延遲的問題一直是有源網絡中致力于要解決的挑戰,在無源網絡中也不例外.如在火山監測預警系統中,因為數據傳輸的長時間延遲而導致沒有及時發現險情,就會造成人員傷害及重大財產損失等嚴重后果.但是,無源節點每一次捕獲的能量和電池所提供的能量有很大差別,已有的用于傳統有源網絡中降低延遲的方法不能直接用在無源網絡中.因此,在節點能夠持續收集能量,但每一次所捕獲的能量都非常小的約束下去提高網絡的延遲性能,以滿足在無源感知網絡中的應用需求很有必要.

然而,現有的路由協議在應用于無源感知網絡環境時,大多缺乏兼顧能耗和延遲性能的考慮.如何設計一種在無源網絡中能夠兼顧能耗和延遲的合理的路由協議,盡可能低地降低節點能耗的同時降低網絡延遲,是本文所面臨的挑戰.因此,本文提出能耗和延遲平衡的機會路由協議(balance of energy and delay opportunistic routing protocol,簡稱EDOR).該協議通過提出節點能耗模型,并考慮轉發節點的鄰居節點占空比的綜合影響來進行路由決策,獲得能耗和延遲平衡的良好效果,并提出合理的退避策略實現數據包被單一轉發節點轉發,來減少通信過程中碰撞帶來的能量和時間的消耗,減少網絡中無效的數據副本數量,延長網絡生存周期和提高數據傳輸效率,以完成在自然條件惡劣的野外環境中的監測任務.

本文的貢獻在于分析了在無源感知網絡中所面臨的挑戰是兼顧能耗和延遲,即在盡可能降低網絡中能耗的同時,如何合理地權衡考慮延遲問題,以提高數據的傳輸效率,使得網絡中的節點達到能耗和延遲平衡的工作狀態.而且,針對這一挑戰提出了能耗和延遲平衡的機會路由協議EDOR.

1 相關研究

近年來,科研人員在能量收集技術方面展開了研究.相比于太陽能、風能等能源,泛在的電磁波是未來無源感知網絡的最主要能量來源之一.科研人員對如何從泛在的電磁波中獲取能量這一問題有了一些研究成果.例如,研究人員在射頻識別(RFID)系統[5]中RFID 閱讀器發送射頻波給周圍RFID 標簽時,RFID 標簽通過捕獲來自閱讀器的射頻能量來驅動內置微芯片工作,并通過調制反射電磁波,將其自身ID 調制在反射電磁波中發送給閱讀器.2007 年,Sample 等人開發了無線識別和感知平臺(wireless identification sensing platform,簡稱WISP)[6,7],它是第一個以射頻讀取器的射頻信號為能量源、且能夠通過反射電磁波將所感知到的數據回復給射頻讀取器.2011 年,Vyas 等人設計了能夠捕獲470MHz～570MHz 頻段射頻能量的電路;用超級電容給微控制器和無線收發器供電,以實現能夠無源自主感知和自主發送數據的無線傳感器[8].2013 年,Parks 等人研究了從無線蜂窩射頻信號和電視廣播射頻信號中捕獲能量的技術,設計出射頻能量捕獲電路,其測試結果表明:所設計的基于能量捕獲的低功耗傳感節點在距離發送功率為1mW 的電視塔約10km 范圍內能夠正常工作[9].Liu 等人進一步研究了無源節點之間的通信技術,使無源節點能夠以泛在射頻作為唯一的能量源來獲取能量,且通過控制射頻信號的反射給鄰近無源節點傳輸數據,實現了1Kbps 傳輸速率[10].

由此可見,從周圍泛在的電磁波中捕獲能量以支持無源感知節點工作,已取得了一些成果.然而,它們無法直接應用于無源感知網絡,其主要原因有兩點.其一,無源感知節點在捕獲能量時存在著瓶頸:儲能單元(如電容)只能儲存非常有限的電量,一旦電容儲存滿電量,就無法繼續捕獲能量;同時,泛在的電磁波信號強度低導致充電過程非常緩慢;其二,感知節點的主要任務是感知環境變化,尤其是捕捉突發事件所產生的物理量,如火災、泥石流等自然災害等,對網絡延遲性能有很高的要求.因此,需要設計合理的路由協議,以實現無源網絡的感知.

傳統的確定性路由協議在應對無線鏈路時存在諸多限制,其固定的路由選擇可能會因為無線鏈路的不穩定性而造成嚴重的性能下降.因此,為了克服確定性路由協議的諸多局限性,機會路由策略被越來越廣泛地使用[11].這類協議充分利用廣播特性,使得在解決不可靠鏈路方面相比傳統路由有著得天獨厚的優勢.該協議使得節點的轉發選擇不再固定,而是很多下一跳節點都可能進行轉發,從而使得網絡性能在能耗、延遲等方面都有所提升.

現有的機會路由協議大多應用在有源節點網絡中,并在發展過程中逐漸形成了五大類別,分別是基于地理信息類、鏈路狀態感知類、隨機類、基于圖論和概率思想類以及跨層設定類.基于地理信息類的機會路由協議,如DTRP[12],LinGo[13]以及COR[14]等協議,利用地理定位信息克服傳感網絡中的基礎設備不足的問題.鏈路狀態感知類的機會路由協議利用無線傳輸的天然廣播特性,通過某種計算標準來交換評估鏈路質量信息并作為轉發決策來提升包傳輸的可靠性,MORE[15]和CCACK[16]等協議都是基于這種思路設計的.而隨機類機會路由協議則是為了應對移動節點的情況,這種網絡環境下節點選擇轉發候選節點時,很難判斷究竟選擇哪個候選節點可以得到低能耗或者延遲,因此采用隨機的策略如OPF[17]以及OOF[18]等策略.隨著前3 種策略的機會路由協議的發展,機會路由算法慢慢成熟.基于圖論和概率思想的機會路由算法是近年來受到關注的新思路,通過結合一些計算機領域的新的研究點來提升協議的性能,例如基于圖論研究的MAP[19]以及基于學習的ORL[20]協議等.最后一類使用跨層策略的機會路由算法則利用底層的信息來輔助路由決策,例如利用物理層信息的EEOR[21]和HS-OR[22]協議、利用MAC 層信息的ORCD[23]和ORW[24]以及利用物理層和MAC 層兩層信息的CL-EE[25]和SCAD[26]協議,這些機會路由協議通過利用下層的關鍵信息來輔助決策,往往能夠取得很好的能耗或者延遲方面的性能.

然而,應用于傳統使用電池的傳感器網絡的路由協議雖然能夠很好地解決有源網絡中的能耗和延遲問題,但卻不能把它們直接應用到無源網絡中來,因為這些方法未能充分考慮無源感知網絡的下述因素:(1) 無源節點每一次所捕獲的能量非常小,這使得節點可以用于探路以及發送數據包的能量極為受限,因此需要盡可能地降低能耗,以確保節點所獲得的能量足以支撐其完成數據傳輸的任務;(2) 在一些無法按期更換電池的應用中,對數據的實時性要求較高,還要提高網絡的延遲性能,否則可能造成嚴重后果.鑒于此,需要設計適用于無源感知網絡的路由協議.而現有的應用于無源感知網絡的機會路由協議并不多,并且由于能量收集型節點能級的不穩定以及相對較長的生存周期,其應用時的側重點和設計思路也有所區別[27].例如,文獻[28]提出的EoR 協議就是在ORW 協議的基礎上進行改進,使其適用于無源感知網絡的特點,并取得了較好的延遲效果;文獻[29]提出的TPGFPlus 協議同樣利用跨層思想降低了延遲;文獻[30]提出的OR-AHaD 協議在無源感知網絡中取得了較低的能耗效果;文獻[31]中提出的協議實現了處理不同延遲要求包的機會路由協議.所以,本文要設計一種適用于無源感知網絡的兼顧低延遲和低能耗特性的路由協議.

2 能耗和延遲平衡的機會路由協議EDOR

在無源感知網絡中,能量不再是唯一關注的因素,對延遲性能的提升,將會使節點向基站發送數據時獲得更高的效率.但現有的路由協議在應用于無源節點的網絡環境時,大多缺乏兼顧能耗和延遲性能的考慮,因此,本節提出能耗和延遲平衡的機會路由協議(EDOR).該協議通過分析節點通信的過程來估算節點的預期能耗值,讓節點選擇令自己能耗較低的鄰居節點作為轉發候選節點.在最終確定轉發節點時,本協議通過結合候選節點下一跳鄰居節點的占空比信息來進行決策,使得發送節點選擇能更快將數據轉發出去的候選節點來降低延遲,獲得了能耗和延遲平衡的良好效果;然后提出合理的退避策略,實現了數據包被單一轉發節點轉發,減少了網絡中無效的數據副本數量.

2.1 EDOR協議設計

2.1.1 機會路由策略

為了減少節點的能耗和延遲,不能使用確定性的路由方法來固定選擇某一個節點作為數據轉發的唯一選擇.因為隨著網絡環境的變化以及無線鏈路狀態的不穩定性,如果選定的唯一下一跳節點與當前發送節點的工作周期恰好交錯開,等待過程會增加節點的能耗和延遲;若節點在等待過程中持續發送探測包消耗了過多能量,可能造成將無源節點上一個周期收集的能量消耗殆盡,使節點得重新進入能量收集階段而無法進行通信.因此,我們考慮使用機會路由策略.

機會路由的主要思路可以總結如下:用Cu表示節點u使用某種機會路由策略向目標節點發包時預計所需消耗的能量,初始階段,目標節點的期望能耗值設定為0,其他所有節點的期望能耗值設定為正無窮.同基于距離向量的路由機制類似,機會路由協議機制中,每個節點的期望能耗值以及轉發列表將會周期性地計算并且更新.當一個節點準備向目的節點發送或者轉發包時,該節點只需簡單地將數據包朝著基站方向廣播出去,并利用一定的選擇策略選擇轉發節點,從而完成整個發送過程[32].如圖1 所示.

Fig.1 Model of opportunistic routing圖1 機會路由傳輸實例

假定發送節點經過兩跳到達目標節點,并且發送節點的下一跳范圍內有v1,v2,…,vn共n個節點.從發送節點到下一跳每個節點的傳輸錯誤率都是en,而下一跳的所有節點到目標節點都是完美鏈路,即傳輸錯誤概率都是0.對于傳統路由方法而言,每次傳輸時,源節點都會選擇固定的節點,比如vi作為下一跳進行傳輸,則根據假設整個傳輸成功所需要的預期次數為.而如果使用機會路由策略,由于發送節點會監聽所有下一跳節點的狀態,只要至少有1 個節點醒來就立刻傳輸數據,因此傳輸成功需要預期次數降到了(證明過程見下).尤其當e值越接近于1,n值也較大時,兩種策略下的預期傳輸次數差距也會越大,消耗能量的差距也就越大.也就是說,機會路由對于鏈路質量較差并且節點個數較多的網絡環境性能有著較明顯的提升.同樣,如果下一跳中哪個節點最先醒來進入工作狀態,機會路由就最先將其選擇為轉發節點的話,整個轉發過程的延遲相較于固定節點也會顯著降低.

證明:假設從發送節點到下一跳每個節點的傳輸錯誤率是e,則傳輸成功率為1?e,在傳統路由方法中,傳輸成功的預期次數即為.當使用機會路由策略時,只要有至少1 個節點醒來時就會立刻傳輸數據,則傳輸失敗的概率為en,因此傳輸成功所需要的預期次數降低為.證明完畢. □

2.1.2 EDOR 協議設計思路

現有的機會路由協議,有些僅從能耗角度出發,雖然取得了不錯的效果,但是完全舍棄了延遲;有些協議則從延遲入手,卻忽略了能耗的計算,這些都不符合使用能量收集型節點的網絡特點.本文提出一種適用于異構占空比網絡下的兼顧延遲和能耗問題的路由協議,該協議整體的設計思路如圖2 所示.

Fig.2 Overview of the EDOR protocol圖2 EDOR 協議設計思路

發送節點通過廣播探測包獲取周圍鄰居節點反饋的關于能耗的信息,確定轉發候選集合.候選集中的節點則根據考慮了延遲因素的通信代價計算標準來決定自己的退避時間,退避時間短的節點即為選中的轉發節點,從而實現發送節點選擇使自己能耗和延遲性能平衡的轉發節點.

2.2 能耗和延遲的影響因素

2.2.1 網絡模型

為了保證整個網絡有著穩定和合適的任務循環周期,同時為了不同類型的節點完成不同的數據采集和傳輸任務,本文設定所有節點擁有相同的總周期長度L和各自不同的占空比Dv.

設定傳感網中所有的節點都有一個獨一無二的id 號i∈[1,n].在野外部署的多跳無線網絡環境下,本文抽象出一個圖的模型,并將其表示為G=(V,E),其中,V代表網絡中n個節點組成的集合,E表示兩個可以直接通信的節點之間的鏈路.比如,對網絡中任意兩個可以直接通信的節點u∈V,v∈V而言,(u,v)代表兩個節點間的一條鏈路,每條鏈路都有一個非負的權值,表示為w(u,v),這個權值代表了節點u給節點v發包成功所耗費的能量,稱其為傳輸功率.這個值根據所處監測環境的不同,以及能量收集型節點能量源的不同而有所區別.由于當節點u以不同的傳輸功率進行通信時,其通信范圍會不同,進而單跳范圍內的鄰居節點個數也會有所差別,因此這種情況下,路由更新的代價將會增大,并且網絡的通信會不穩定.因此對節點i,為了整個監測網絡的穩定傳輸,假定在其通信過程中擁有的傳輸功率w保持不變.本文以NW(u)用來表示當節點u以w能量進行通信時它的鄰居節點的集合,為了簡化起見,當節點以設定好的傳輸功率進行通信時,省略下標W,記為N(u).另外,現實環境部署情況下節點間的通信鏈路不可能是完美鏈路,將每條鏈路(u,v)的傳輸不成功的概率表示為euv.通過以上假設可以得出:對每一個節點u,其傳輸一次至少會消耗w(u,v)的能量,并且傳輸成功的概率為1?euv.為了提升網絡性能,接下來,本文將從影響能耗和延遲的因素對協議的設計進行分析.

2.2.2 節點的預期能耗

雖然無源節點的生存周期得到顯著延長,但并不意味著其能量可以無限使用.在路由過程中,選擇能量消耗少的節點更有利于網絡的長期生存.我們首先研究了將節點發包時的預期能耗計算標準(expected consumed cost,簡稱ECC)來作為發送節點選擇轉發候選節點的依據.

機會路由通信過程中,考慮從當前節點的下一跳節點中有節點收到包時到轉發出去為止這一整段過程,主要分為以下兩個部分:一部分為當前節點向其轉發候選集廣播探測包發現候選節點時,其下一跳節點中至少有1 個節點接收到這一過程,由于受鏈路質量以及能量收集型節點剩余電量的影響,可能出現下一跳節點均未成功接收發送節點信息的情況,該部分能耗稱為失敗代價;另一部分則是轉發候選集中至少有1 個節點成功將該包轉發出去這一過程,該過程的能耗稱為轉發代價.針對這兩個過程,本文將分別討論其能耗的計算標準.

(1) 失敗代價

如果U表示一個節點集合,那么Usort表示一個節點集合,其中所包含的節點與U相同,但其中的元素排布順序按照每個節點向某一個固定的目標節點發包時的期望能耗升序排列.假定Fwd(u)表示節點u的轉發候選集(該轉發候選集的選擇策略將在下一節進行討論),那么Fwdsort(u)表示候選集中的點已經按照其期望能耗升序排列.例如,如果i

其中,vi表示屬于集合Fwdsort(u)中的任意一個節點,SumFwd表示Fwdsort(u)包含的節點個數.

當前節點u是以w的能量功率進行每次通信過程,即發包消耗的能量為w.令表示節點u發包給候選集中至少1 個節點預計消耗的能量,由于w消耗能量的過程是在該節點發送的包成功被其轉發候選集中節點接收到的情況下假定的,因此該過程中實際消耗的能量為

(2) 轉發代價

當前節點的候選集中有至少1 個節點成功收到發送的包后,這時進入了轉發階段.這個階段經歷的過程如下:首先選擇候選集中優先級最高的節點作為下一跳完成轉發過程(候選集的節點選取和建立過程以及候選集中節點優先級的確定方法將在下一節詳細討論),如果轉發未能成功完成,在不考慮重傳的情況下,則繼續選擇優先級第二高節點進行轉發,以此類推,直到至少有1 個候選節點完成了轉發過程.同時,在節點轉發過程中,轉發代價中已經包含了節點由于占空比導致的等待和空閑監聽帶來的消耗.因為當前節點向下一跳轉發數據時,當前節點的工作周期需要與下一跳節點的工作周期對應上,若兩個節點的工作周期沒有對接上時,當前節點就會等待下一跳節點醒來時,再完成轉發過程.

假定節點u的轉發候選集已經按照其中節點的預期能耗值按升序排列得到了含有優先級的轉發候選集,則首先選擇其中的第1 個節點進行轉發,如果沒有成功,則選擇第2 個節點,依次類推.由此可以得到第1 個節點v1將以的概率成功轉發,并消耗的能量,節點v2則將以的概率成功轉發并消耗的能量.由于該過程同樣建立在候選集中至少有1 個節點成功接收的基礎上,則該過程中預期消耗的能量可通過公式(3)計算.

令Cu表示節點u通過轉發候選集發包過程中產生的預期能量,那么通過前文分析可知,即

2.2.3 轉發候選集的選擇策略

機會路由過程中,合適的轉發候選集的選擇策略將會對網絡性能的提升產生重要影響.本節提出一個基于ECC值的轉發候選集選擇策略.

首先,當前節點u的轉發候選集合是其鄰居節點集的子集,即Fwd(u)?N(u).轉發候選集合中節點的數目的增加對發送節點的預期能耗將會產生以下影響.

(1) 增加候選集中的節點數目,將會使得當前發送節點的轉發候選變多,從而提高至少1 個節點接收到探測信息的可能性,對發送節點的失敗代價產生正面的收益.

(2) 轉發候選集中節點數目過多,也可能會將與當前發送節點通信鏈路失敗率較高的節點或其本身預期能耗較高的節點加入轉發的候選集,導致通信質量不好的節點加入候選,如果發送節點選擇其作為轉發節點,將會對轉發代價帶來負面的收益.

因此,如何在當前節點的鄰居節點集中選擇合適的節點加入轉發候選集,是降低節點能耗的關鍵過程.

在確定轉發候選集的過程中,已知當前節點u的鄰居節點集N(u),該集合中每個點的預期能耗值以及節點u與每一個鄰居節點間傳輸成功的概率,于是,當前的問題轉化為如何找到合適的轉發候選集Fwd(u)?N(u),使得發送節點的預期能耗Cu值最小.假設當前節點u的鄰居集中的節點已經按照其預期能耗值進行了升序排列,并將這個排好后的鄰居集記為Nsort(u),于是可以得到如下定理.

定理1.對當前節點u而言,如果現在起鄰居集中有一個節點vk不屬于當前已經確定的轉發候選集,即vk?Fwdsort(u),那么如果,則

定理2.對當前節點u而言,如果現在起鄰居集中有一個節點vk不屬于當前已經確定的轉發候選集,即vk?Fwdsort(u),那么,如果,則Cu(Fwdsort(u)∪{vk})>Cu.

證明:根據公式(4)可知,節點u當前的ECC值為

嘗試加入鄰居節點vk后,節點u的ECC值更新為

于是,兩項相減可得:

則通分后可得:

兩個定理共同指出,為了使當前發送節點的ECC最小而判斷一個鄰居節點是否可以加入當前節點的轉發候選集時,根據自身不斷更新的ECC值即可:如果該鄰居節點的ECC值小于當前候選節點集情況下確定的發送節點的ECC值,則加入該鄰居節點到候選集中會使發送節點的ECC值變小,所以策略上應該將該鄰居節點加入轉發候選集;反之,當該鄰居節點的ECC值大于當前候選節點集情況下確定的發送節點的ECC值,則不加入該節點.由于Nsort(u)中的節點已經按照ECC值升序排列,因此當發送節點遇到第1 個大于當前ECC值的鄰居節點時,轉發候選集的構建便宣告完畢.下面是創建當前發送節點u的候選集的算法描述,通過該算法確定的轉發候選集會將通信過程中預期能耗較大的節點剔除,使得當前節點在能耗較低的鄰居節點中選擇轉發節點.

算法1.構建轉發候選集.

輸入:N(u)中所有節點的EEC值.

輸出:當前節點的EEC值Cu以及轉發候選集Fwdsort(u).

顯然,該算法中存在一個以鄰居節點個數為長度的循環,并且節點最多需要保存所有鄰居節點,因此,該算法的時間復雜度和空間復雜度均為O(SumFwd).

2.2.4 占空比對延遲的影響

為了降低節點能耗的同時降低延遲,在利用ECC值完成了轉發候選集的構建之后,本協議還需要考慮節點運行的整個過程中,影響延遲的因素.

大多數文獻和現有機會路由方法中考慮節點能耗和延遲時只從通信過程入手,分析從下一跳節點中至少有1 個節點收到包時到轉發出去為止這一段過程中,就是上一節中討論過的組成ECC度量標準的兩個部分.然而當考慮如下情況時:一個節點跟另一個節點進行通信,如果其工作周期與另一個節點的工作周期沒有對接上,那么發送節點就得不停地發探測包等待該節點醒,這樣會增加網絡延遲.這一部分可以稱為等待代價,如圖3 所示,發送節點前3 次探測,接收節點都處于休眠狀態,直到探測到第4 次才成功遇上接收節點的工作周期,因此整個傳輸分為前后兩部分過程.本次傳輸的延遲也如圖3 所示分為等待過程和通信過程兩部分.文獻[22]中提出了一種考慮等待代價的路由協議,其思路是利用MAC 信息進行跨層處理,本文參考其方法并做出了改進.

Fig.3 Waiting cost during transmission圖3 節點發送過程中等待代價示意圖

當前節點發送數據時,由于使用了基于CSMA 的MAC 層協議,因此必須通過探測的方式來進行通信.然而當真正選擇某個節點進行轉發時,考慮該節點獲得數據后再向后進行轉發的過程,顯然是該轉發節點的鄰居節點的工作周期覆蓋越全面,該轉發節點發送數據時的等待時間就越短,延遲就越低,如圖4 所示.

Fig.4 Waiting costs in the network layer圖4 網絡層中的等待代價示例

當前節點有兩個鄰居節點A和B,而A,B分別擁有兩個和3 個下一跳的鄰居節點,其中,A的兩個鄰居節點的占空比分別為50%和60%,B的3 個候選節點的占空比為10%,20%和10%,并且工作周期在總周期中的位置如圖中所示.因此可以看出,如果選擇A節點進行轉發,那么A節點在下一跳時可以很快將數據繼續轉發下去(因為A節點的鄰居節點的占空比之和達到了100%);如果選擇B節點進行轉發,則意味著B拿到數據后有70%的時間是不能直接轉發的,必須等待候選節點的蘇醒(因為B節點鄰居節點之間除去重疊部分,其占空比之和只有30%).因此,如果按照ECC的值排序,B的預期能耗小于A,從而優先選擇B進行轉發的話僅僅是在當前情況下的最優選擇,而在進行到下一跳的轉發過程時,B的選擇代價是大于A的.因此當轉發候選集確定后,具體選擇哪個節點進行轉發,本文協議考慮了通過轉發候選節點的鄰居節點占空比之和的判斷因素.

在節點的每個周期中,易知其周期性醒來工作的時間為Twake=L×Du.假設使用表示轉發候選集中節點i和j醒來時間的重疊部分,那么對于該過程的等待代價而言,所有鄰居節點除過重疊部分的占空比之和越大,該節點進行轉發時的等待代價就越低.可以通過公式(10)計算對當前節點u的所有鄰居節點的有效工作時間占總周期的比例RoFu:

在上式的分子表示的時間段內,由于鄰居節點中總有節點是處于喚醒狀態,因此在該時間段內,當前節點總是能夠立刻將數據發送出去.而等待階段則由于沒有任何一個候選節點處于喚醒狀態,故當前節點的等待時間所占總周期的比例RoWu為

可以看出,轉發候選節點的RoWu越小,其等待代價越小,節點發送數據的延遲也就越小.

2.3 EDOR協議原理

2.3.1 協議概述

上一小節中討論了在異構占空比網絡中影響節點能耗和延遲的因素,為了達到平衡能耗和延遲性能的目的,本節提出綜合能耗和延遲代價的機會路由協議.

本協議主要分為探測鄰居節點、構建轉發候選集以及選擇轉發節點這幾個過程.其中,探測鄰居節點即為廣播探測包獲取鄰居節點ECC值以及RoW值的過程,而轉發候選集將根據第2.3.3 節中提出的轉發候選集選擇策略來構建.接下來,本節將重點討論選擇轉發節點的過程.

2.3.2 轉發代價Cost

本協議使用Cost值作為節點的通信代價來作為轉發節點的選擇標準.考慮轉發代價時,為了實現平衡能耗和延遲的目標,該值將通過各個轉發候選節點的ECC值以及RoWu來聯合確定.

RoWu的值顯然處于[0,1]之間,因此當候選集確定后選擇轉發節點時,也必須將傳輸代價的值歸一化到[0,1]區間內.假設由算法1 確定的轉發候選集中存在n個候選節點,其ECC值分別為,則對轉發候選節點vi而言,通過公式(12)將其進行歸一化處理.

于是,真正衡量轉發候選節點通信代價標準的Cost值將由公式(13)計算.

其中,系數a的數值將決定能耗因素和延遲因素的占比,將在評估與實驗章節通過仿真實驗來具體驗證確定.轉發候選集中Cost值最低的節點,即為應該選擇的轉發節點.

2.3.3 轉發節點退避策略

這一節中,本協議討論當前發送節點如何將數據單播給通過上一節方法選定的轉發候選節點,從而減少網絡中無效數據副本的數量.利用無線傳感網絡的廣播特性,當前節點可以很容易將數據包發送給轉發候選集中的節點,但這樣也會造成潛在的問題:如果一個數據包被很多候選節點收到而沒有合適的退避處理策略的話,這些候選節點將都給發送節點回復ACK,會大大提升碰撞的可能性,造成不必要的能量消耗;即便合理地使用了退避策略,如果一個候選節點不知道已經有其他候選節點完成了轉發而選擇繼續轉發,就會使同一個數據包在網絡中存在很多不必要的副本,造成能量浪費和無效吞吐.針對這些問題,本協議提出基于選擇策略度量值Cost的退避策略以及ACK 壓制策略.

為了減少碰撞帶來的能量和時間消耗,本協議利用Cost值設計一種退避策略.當發送節點確定了自己的轉發候選集并計算出ECC值后,該節點發送數據時將轉發候選集中最大的ECC值Cmax以及轉發候選集中所有節點的ECC值之和包含在內.收到數據節點通過與自身的ECC值進行對比:如果,則該鄰居節點將自己選為轉發候選節點,并在回復ACK 之前執行退避過程.該節點的退避時間應該同Cost值成正比,假設Bmax是MAC 層預設的最大的隨機退避時間,那么對候選集中的節點vi,其退避時間由公式(14)計算:

通過這種退避機制,候選集中代價最小的節點將會退避最短的時間,即其擁有了最高的轉發優先級.當其退避時間結束后,將優先廣播ACK 信息.這樣,當發送節點接收到第1 個ACK 信息時,得知其數據包已經被成功接收.而其他收到該數據包的轉發候選節點由于退避時間較長,在其退避時間內如果收到了來自其他節點的數據包ACK 信息,則該節點將收到的數據包丟棄,不再進行轉發和回復.通過這樣的退避以及ACK 壓制策略,本協議就實現了發送節點把數據單播給某一選定的轉發節點,從而減少了該過程中額外的能量消耗.

2.3.4 網絡初始化

在網絡第1 次啟動時,整個網絡的初始建立過程將從基站(sink)開始到邊緣節點,直到每一個節點都完成自身的初始化過程后進入休眠狀態為止.每個節點在其初始化階段保持工作狀態不休眠,直到完成該節點的初始化過程后將休眠一整個時間周期L,之后,將根據其設定好的占空比開始正常的工作周期.

當網絡初始化開始時,基站首先向全網發送廣播信息.廣播信息中包括其占空比D、ECC值C和其等待代價度量標準RoW(對基站而言,由于其是組網的第1 個節點并且不休眠,因此Dsink=100%,Csink=0,RoWsink=0).因為sink 是該網絡中所有數據包的歸宿,因此收到其廣播包的節點都將其視為自己的下一跳以及轉發唯一的轉發候選節點,并據此計算自己相應的ECC值.計算完畢后,為了防止碰撞消耗不必要的能量,每個節點隨機退避一個時間后,繼續將含有自己占空比和ECC值信息的包廣播出去.節點廣播之后,將會監聽一段時間(T1)來確認自己的包是否被至少1 個節點接收到,如果沒有問題,節點將休眠一整個周期.

對于網絡中距離匯聚節點兩跳及以上的節點u,當其接受到其他節點廣播包中的信息時,將其id 號加入到自己的鄰居節點集N(u).當經過一段監聽時間(T2)不再收到廣播信息時,利用前文中提出的轉發候選集構建方案,將N(u)中的節點按C值排序后依次嘗試加入并最終形成候選集Fwdsort(u),同時計算出該轉發候選集情況下當前節點的預期能耗值Cu,并根據當前時間和廣播包中的占空比信息計算出節點的RoWu,以便為之后的轉發決策服務.通過每個廣播包,可以計算該發包節點(即轉發候選節點)下次醒來的時間為

則其工作時間的范圍即為

通過此計算方法,還可以估算出不同發送節點占空比的重疊部分,從而計算出當前轉發候選集情況下節點u的RoWu值.之后,當前節點同樣隨機退避一個時間之后將自己的占空比D、ECC值C及其等待代價度量標準RoW值加入包中廣播出去,廣播完成后,使用同樣的機制監聽一段時間(T1)進入休眠.同理,網絡中每個節點在網絡初始化過程中都執行這樣一整套流程后,整個網絡初始化過程結束.這時,網絡中每個節點的轉發候選集以及等待代價度量標準RoWu都得以確定.

2.3.5 網絡通信過程

當網絡的初始化過程完成后,網絡中的節點將陸續醒來進行發送或轉發數據包的工作.當一個節點有數據包要發送時,首先廣播探測包,然后利用收到回復的節點中根據其ECC值參考前文提出的算法選擇是否加入轉發候選集.由于初始化過程結束后網絡中節點的ECC值是按照遠離匯聚節點逐漸增大而排布的,因此根據算法中加入候選集的節點都是ECC值小于當前值這一規則,可以避免將上一跳的節點加入候選集而形成路由環路.當前節點也隨著候選集中節點的不斷加入而重新計算自己的C值,直到不再有可以降低本身ECC值的節點出現時,當前發送節點的轉發候選集就確定了.轉發候選集的確定會使一部分能耗代價較高的鄰居節點被排除,這樣可以降低節點之間通信的能耗.之后,轉發候選節點通過公式(13)計算出的Cost值執行退避,從而完成轉發過程.在此過程中,把轉發數據的延遲降到最小.如圖5 所示為一個節點通信過程示例.

Fig.5 Example of communication process圖5 通信過程示例

如圖5 所示,Sender 為發送節點,其含有3 個鄰居節點A,B,C;同時,節點A有3 個鄰居節點B,D和E,節點B有鄰居節點A,C,E和F,節點C的鄰居節點為B,F,G,H.Sender 首先廣播探測包,假設得到節點A,B,C回復的各自的ECC值分別為1,1.5 和3.假設發送節點同A,B,C之間鏈路的錯誤率都為0.5,而發送功率為1.

(1) Sender 根據ECC值將A,B,C節點從小到大排序,首先將節點A加入轉發候選集,并計算出自己當前的ECC值為3;之后比較節點B的ECC值小于3,于是將B也加入轉發候選集,重新計算自己的ECC值為2.25;此時發現節點C的ECC值大于當前計算出的ECC值,于是不將C值加入,轉發候選集構建結束,將能耗代價較高的鄰居節點C被排除,降低節點之間通信的能耗.

(2) Sender 將轉發候選集中節點最大的ECC值1.5 作為閾值和所有ECC值之和2.5 加入數據包進行廣播,收到數據包的節點A,B,C將自己的ECC值與閾值1.5 進行對比,其中,節點A,B發現自己的ECC值小于等于該閾值,于是將自己視為轉發節點,準備執行退避后轉發,節點C則丟棄該數據包.

(3) 節點A,B根據退避計算公式計算自己需要退避的時間,如果節點A退避時間短,則首先廣播ACK,Sender 節點收到ACK 后得知轉發成功;而節點B收到A的ACK 則得知自己的轉發優先級較低,于是丟棄收到的數據包,使得轉發數據的延遲最短,實現能耗和延遲的平衡.

在該過程中,單個節點的占空比雖然不會發生變化,但是由于網絡中鏈路質量有可能改變,從而造成節點的鄰居節點集可能發生變化;并且由于時鐘累計后出現誤差現象的存在,節點的鄰居節點工作周期的重疊部分也可能發生變化,這些都可能改變一個節點的RoW值,從而影響路由決策.為了解決這個問題,本協議設計了更新節點RoW值的策略:初始化階段時,鄰居節點回復發送節點時會捎帶自己的占空比等信息;而在網絡結束初始化過程開始正常運行時,鄰居節點將在回復的信息中添加一項Tpass,代表其睡醒后經過的時間;而發送節點接收到后,可以根據自身的時鐘來修正時鐘漂移帶來的誤差.

3 實驗設計與分析

為了驗證所提出的路由協議的有效性,本文利用Omnet++仿真平臺在MAC 層使用CSMA 的基礎上對EDOR 協議進行了多組實驗.由于能量收集型節點的能量收集過程對上層來說是隱藏的,并且該過程也不是本協議研究的范疇,因此本文使用占空比較高的節點模擬代替能量收集型節點,并研究所提出的EDOR 協議的能耗和延遲性能.

本文對不同數量、不同占空比類型的節點組成的網絡環境都進行了測試.由于本協議適用于擁有相對較高占空比的能量收集型節點,因此將使用4 種不同占空比類型的節點,分別是占空比為40%,30%,20%以及低于10%的節點.實驗中使用N-X%-Y%-Z%分別表示節點的總個數為N、占空比為40%的節點占比為X%、30%的占比為Y%、20%的占比為Z%、其余為占空比低于10%的節點.所有節點的總周期長度L一致,其他一些網絡設置的關鍵參數見表1.

Table 1 Settings of network parameter表1 網絡參數設置

3.1 系數確定實驗

為了確定轉發候選節點選擇標準Cost值計算公式中的系數a,本實驗將系數a在[0,1]的區間內每次變化0.1,從而產生11 組對比數據;同時,利用OMNeT++平臺的拓撲產生器隨機產生6 組不同規模和節點類型的拓撲,見表2.

Table 2 Example of test networking表2 測試網絡示例

本文首先對端到端延遲進行了仿真實驗,得到了如圖6 所示的結果.從圖中可以看出,隨著Cost值計算公式中系數a取值的不斷增大,不同的網絡拓撲均表現出延遲上升的總體趨勢.這時,因為隨著系數a取值的增大,RoW值在Cost中的占比就越來越小,因此在對轉發候選集中的節點進行選擇時,候選節點的鄰居節點占空比之和對決策的影響就越小,發送節點更傾向于選擇能耗較小而不是延遲較低的節點進行轉發,因而端到端延遲隨之變大.同時可以看出,隨著節點個數的增多,每個節點鄰居節點數目的增多,網絡中平均延遲的數值是在減小的.對于具有相同節點數目的網絡T4,T5,T6,則隨著網絡中高占空比節點數目的增加使得通信節點之間工作周期相遇的概率提升,從而延遲減少.

對于節點的能量消耗問題,本實驗使用發包的數量來模擬衡量.本文使6 組網絡分別仿真相同的時間,在同樣的時間跨度內,發包次數越多,代表節點處于工作狀態的時間越長,進行的通信過程越多,從而能耗越大.結果如圖7 所示.

從圖7 中可以看出,隨著系數a值的不斷增大,Cost值計算中關于ECC值的占比不斷上升,即發送節點在從轉發候選集中選擇轉發節點時,會更傾向于能耗較少而不是延遲較低的節點進行轉發.因此,節點平均發包數量整體在減少.同時還發現,在T1和T2的網絡情況下,發包數量的下降并不明顯.這是因為在網絡中節點數量較少時,每個發送節點的鄰居節點以及選定的轉發候選中的節點數量都不會很多,在轉發候選集選擇過程中已經將能耗較大的節點排除在外的情況下,節點發包數量的變化并不明顯.而隨著網絡規模的擴大,能耗下降的趨勢就逐漸顯現出來.從圖中可以看出,隨著網絡中節點個數的增加,節點的平均能耗也會增加.這是由于隨著鄰居節點個數的增多,節點的通信頻率增加造成的.T5,T6相比于T4則是隨著網絡中高占空比節點數量的增加,能耗相應增加.

Fig.6 Average delay of end-to-end圖6 端到端延遲平均值

Fig.7 Average number of packets圖7 發包數量平均值

從兩個圖中可知,隨著系數a的增大,節點的延遲和能耗的整體變化趨勢是相反的,這符合前文的分析和設定.由于轉發候選集的確定已經使得一部分能耗代價較高的鄰居節點被排除,因此在從轉發候選集中選擇轉發節點時,本協議更傾向于考慮降低延遲.從圖中可以看出,a值處于[0,0.4]范圍時,延遲相對處在較低水平,能耗則在a值取得0.2 開始,T4,T5,T6均出現較明顯的能耗下降,因此本協議選擇a值為0.2.

3.2 單一轉發節點驗證實驗

為了減少網絡中無效的數據副本數量,本文協議設定了從轉發候選集中選擇單一節點進行轉發的退避過程.對6 種隨機網絡拓撲,分別測試了每個數據包被轉發的次數,以此來驗證該退避過程對于確定單一轉發節點的有效性.仿真結果如圖8 所示.

Fig.8 Average number of forwarding nodes per hop圖8 每跳平均轉發節點個數

從上圖中可以看出,隨著網絡拓撲規模的增大,真正轉發數據包的節點有所增加,但總體基本接近于一個.這時,由于雖然本文協議使用基于Cost值的退避來選擇唯一轉發節點,并且利用Cost值較小的節點,使用ACK壓制了其他轉發候選節點,但是因隱藏終端問題的存在,有可能被選中的轉發節點發送的ACK 無法被所有轉發候選節點收到,而誤以為自己是被選中的轉發節點.這種情況出現的次數隨著網絡規模的擴大、鄰居節點數目的增多而增加,因此使得有些數據包可能會被兩個節點轉發.然而,因為在轉發候選集的構建過程中已經排除了一部分鄰居節點,剩余的加入轉發候選集的節點彼此之間不在通信范圍內的概率很低,所以出現兩個轉發節點的概率很低,兩個以上的情況幾乎沒有.因此,本文協議基本實現了數據包單一轉發的功能,從而有效減少了網絡中的無用副本.

3.3 對比實驗

3.3.1 延遲比較

為了驗證本協議(EDOR-Cost)的有效性,實驗中對比了同樣是機會路由的比較經典的ORW 協議(ORWETC)以及對其進行改進的EoR 協議(EoR-ETC),從平均延遲和平均能耗兩方面,同樣使用了6 種隨機網絡拓撲進行了對比實驗.

本文對6 種網絡拓撲下3 種方法的端到端延遲和單跳延遲進行了實驗,結果如圖9 和圖10 所示.

Fig.9 Comparison of the average end-to-end delay圖9 平均端到端延遲比較

Fig.10 Comparison of average one-hop delay圖10 平均單跳延遲比較

從兩圖中可以看出,無論是端到端延遲還是單跳延遲,本文提出協議的延遲都在ORW 和EoR 方法之間,并且更靠近延遲較低的EoR 方法.因為ORW 只是根據候選節點的下一跳鄰居節點的個數來進行選擇,相當于忽略了等待過程產生的代價,其選擇的轉發節點并不是下一跳轉發時延遲較小的節點.而EoR 方法則充分考慮了節點自身和其轉發候選節點占空比的情況,在進行選擇時相比ORW 方法提升了延遲性能.本文的方法EDOR綜合考慮了節點的能耗和延遲兩方面因素,在平衡兩者的同時,在延遲方面取得了接近EoR 方法的良好效果.

3.3.2 能耗比較

本文隨機選取了網絡拓撲T3來比較3 個協議的節點能耗.為了使得能耗的數值更貼近于數據收集網絡的實際情況,選取基站收集到同樣數量的數據包時,節點產生的平均能耗,即當基站收集到相同數量的數據包時,節點平均能耗更低的協議可以使得網絡能夠更好地完成收集任務.能量收集型節點的能量級別很低,節點一次發送或接收過程產生的能耗在10?1mA 甚至微安級別,本實驗根據文獻[33]中提供的參考,將節點進行一次發送和傳輸的能量消耗分別設定為0.56mW 和0.67mW 進行仿真實驗,得到的結果如圖11 所示.

Fig.11 Comparison of average energy consumption圖11 平均能耗比較

由上圖可以看出,隨著基站收集到的包的數量的增加,節點的能耗基本呈線性增加的趨勢(前提是該節點擁有足夠的能量).其中,EoR 方法由于減少了節點的平均等待時間,使得不用頻繁地發送探測包或者監聽信道,從而能耗情況也優于ORW 協議.而本協議由于能量模型的存在,轉發候選集中選擇的節點都向后轉發時預計能量消耗較少的節點,因此取得了最優的能耗特性.

4 總結與展望

針對于無源感知網絡,本文提出了基于綜合能耗和延遲代價的機會路由協議,利用節點的預期能耗模型以及單一轉發節點選擇策略,平衡了節點的能耗和延遲.通過仿真實驗,證明了本文提出的協議取得了良好的能耗和延遲效果,并且成功降低了網絡中的無效數據副本數目.在實驗方面,將研制自己的無源感知節點,考慮在HitchHike 的基礎上做進一步的改進,參考WISP5 上的energy harvesting 部分的電路,使用能量收集技術,結合無線能量獲取與太陽能,為系統構建專門的軟件,通過指令集優化系統,節約能耗,對實驗加以擴展.