基于三維胞元空間的能量高效性多通道協作路由算法

劉俊延 孫 暉柯 濤 路 揚

(浙江大學電氣工程學院 杭州 310027)

1 引言

近年來，無線傳感器網絡(Wireless Sensor Network, WSN)被廣泛應用于智能交通、農業監測、軍事監控等領域[13]-。路由算法作為WSN應用的重要環節，一直是研究熱點之一[4,5]。相比其它的路由算法，基于地理位置信息的 WSN路由無需消耗額外的能量和存儲空間建立和維護路由鏈表，更加符合WSN路由的設計要求[6]。

基于地理位置信息的路由算法中，Fin[7]提出的貪婪(greedy)路由是有效的路由法則，但是貪婪算法會導致遇上局部最小節點后無法繼續路由的情況。Choi等人[8]通過鑒定空洞邊界有效地避開了局部最小節點，但傳遞路徑迂回且延時較長；文獻[9]提出了3D-GPR(Grad Position-based Routing)算法，但沒有考慮3D-WSN中的空洞問題，其實質仍然是貪婪算法。節點能量的耗盡是引起網絡空洞的重要原因，文獻[10]中研究了節點的協作傳輸及能量效率，提高了節點的路由效率，但是沒有從整體上平衡網絡的能耗；文獻[11]提出了 3D-CSR(Cell Space Routing)算法，該算法有效地提高了 3維空洞網絡的發送率，在一定程度上平衡了整個網絡的總能耗，但是沒有從整體上提高能量效率。

本文在3維胞元空間模型的基礎上提出了多層胞元通道模型，并提出了 3D-EEMCR算法。路由方面，通過定義主通道和輔助通道相互協作周邊模式來繞過空洞區域；能量方面，算法權衡考慮節點的剩余能量和位置信息來自適應選舉胞父節點。

2 算法模型

2.1 網絡模型

2.1.1 3維胞元空間模型 3維胞元空間[11]的模型結構如圖 1所示。節點通信半徑為 r，且 r∈[0,Rmax],Rmax為節點的最大通信半徑。節點 i的位置坐標記作(xi,yi,zi)，其所在胞元位置記作(XI,YI,ZI)，胞元的邊長記作d。以X軸坐標為例，節點坐標與胞元坐

圖1 3維胞元空間模型

標的換算方法如式(1)所示：

將不存在有效傳感器節點的胞元定義為空洞胞元，否則為非空洞胞元。非空洞胞元中的胞父節點充當路由器功能，實現胞間路由；胞子節點僅能與本胞元內的胞父通信。

2.1.2 多層胞元通道模型 定義多層胞元通道模型如下：

(1)主通道(Main Channel, MC)：路由模式由貪婪(greedy)模式轉換為周邊(perimeter)模式時，局部最小節點P所在的胞元層，即W=WP。

(2)輔助通道(Assistant Channel, AC): W=WP+1和所在的胞元層，并分別記作上層輔助通道(ACA)和下層輔助通道(ACB)。

(3)消息包傳遞法則：當前節點 C位于主通道(MC)時，消息包可以傳遞至主通道的其它節點或輔助通道的節點；當前節點C位于輔助通道(AC)時，消息包可以傳遞至本輔助通道的其它節點或主通道中的節點，為了避免形成死回路，當消息包傳遞至另一層輔助通道或其它3層通道外的節點時直接丟棄該消息包，如圖2所示。

(4)主通道優先法則：當用逆時針法則選擇下一跳胞元時，若主通道和輔助通道中的胞元同時滿足要求，則優先選擇主通道上的胞元作為下一跳胞元。

(5)輔助通道距離優先法則：當用逆時針法則選擇下一跳胞元時，上下兩個輔助通道中的胞元同時滿足要求，則選擇距離目的胞元較近的一個通道上的胞元作為下一跳胞元。

圖2 消息包傳遞法則

2.2 節點能耗模型

根據自由空間中的通信模型[12]，當消息包大小為q bit，當前節點C的下一跳節點為N，則節點C的發射能量表達式如式(2)所示：

3 3D-EEMCR算法

3.1 自適應胞父選舉機制

算法初始化時，各節點根據式(1)將所有胞元位置相同的節點自動成簇，并指定本胞元內初始能量Eint最大的節點作為胞父節點。

當胞父的剩余能量Eres下降至αEint或時，則由胞父節點觸發選舉。其中為低能量閾值系數，為死亡閾值系數。胞父觸發選舉后，首先根據胞元中節點的剩余能量 Eres確定候選胞父節點，然后根據所有候選胞父節點自身的剩余能量 Eres和節點位置來選擇合適的節點作為胞父節點。假設本胞元內有m個候選胞父節點，該胞元的鄰居胞父個數為 n，則定義胞父選舉變量為 G，其表達式為

3.2 胞元路由機制

路由模式包括貪婪模式和周邊模式，其初始化模式為貪婪模式。當消息包傳遞至局部最小節點時，路由模式切換至周邊模式。

3.2.1周邊模式初始化 路由模式換至周邊模式時，需對重要參數作如下初始化：

返回貪婪模式判據：進入周邊模式時，計算局部最小節點P所在胞元坐標到目標節點D所在胞元坐標的距離，記作。若，則消息包返回貪婪模式。

圖3 胞父選舉流程圖

確定主通道(MC)：消息包傳至局部最小節點P，計算P節點所在胞元位置(UP,VP,WP)與D節點所在胞元位置(UD,VD,WD)的坐標差值，記作(UPD,VPD,WPD)，選取差值最小坐標軸的P點坐標作為主通道胞元層，如圖4所示。

圖4 主通道胞元層選定

環路判據(P, Q)：由主通道的定義可知局部最小節點P位于主通道胞元層中，當為主通道胞元層時，以P為軸，PD在UOW面的投影P'D'為旋轉邊做逆時針旋轉。逆時針旋轉至第1個非空洞胞元即為下一跳胞元，其胞父節點記為 Q，若主通道和輔助通道的胞元同時滿足要求，則遵循主通道優先法則和輔助通道距離優先法則。當再次依次經過(P, Q)節點時，立即丟棄該消息包；

3.2.2 多通道逆時針法則 多通道逆時針法則的一般過程：

(1)確定當前節點C的位置，并根據多通道模型中消息包切換規則確定下一跳胞元所在的胞元層。將可能的下一跳胞元層等效為單層通道；

(2)將當前節點C的前一跳節點記作A，逆時針法則以C為軸，CA在通道面上的投影C'A'為旋轉邊做逆時針旋轉，旋轉至第1個非空洞即為下一跳胞元，當主通道和輔助通道的胞元同時滿足要求時，則遵循主通道優先法則和輔助通道距離優先法則；

4 仿真實驗與結果分析

4.1 仿真環境及參數設置

本節利用 OMNeT++V4.1平臺對算法進行仿真。節點布置的區域設置為體積為160 m×160 m ×160 m的立方體，其中胞元邊長d為20 m，最大通訊半徑Rmax為69.3 m，每個胞元中的節點數N在[0,隨機產生。傳輸放大系數設為，發送單位數據包的電路損耗EELEC為50 nJ/bit，數據處理能耗EC為10 nJ，權重η和λ均設為0.5。每個消息包源節點和目的節點的個數均設為1，大小設為 1 bit，在消息包丟棄時產生新的消息包。在仿真實驗中，通過構造不同體積的中心空洞區域(空洞區域沒有傳感器節點)和不同密度的節點分布，以檢驗 3D-EEMCR算法在不同環境下的消息包發送率，平均能耗以及網絡的存活率。

4.2 仿真結果分析

3D-EEMCR, 3D-GPR和3D-CSR的消息包發送率隨空洞體積變化的曲線對比如圖6所示。在圖6(a)，圖6(b)和圖6(c)中，設單個胞元內的節點數N為0或1，其中取N=1的概率分別為0.75, 0.67, 0.50。在圖6(a)和圖6(b)中，節點的密度較大而網絡中的隨機空洞較少，由于 3D-EEMCR算法使用多層胞元協作路由來繞過空洞區域，致使其發送率始終維持在95%以上；而3D-CSR算法使用單層胞元結構的周邊模式，故消息包發送率較 3D-EEMCR算法下降了5%~15%；而3D-GPR算法遇到局部最小節點就丟包，所以其消息包發送率最低，并隨空洞體積增大呈現直線下降的趨勢。在圖 6(c)中，節點的密度較小而網絡中的隨機空洞較多，故3種算法的發送率均有較大程度的下降，但是 3D-EEMCR算法的發送率較其它兩種算法依然有明顯的優勢。

平均能耗是指網絡總能耗與成功發送的消息包個數之比。3種算法的平均能耗隨空洞體積的變化曲線對比如圖7所示。在圖7(a)中，隨著空洞的不斷變大，3D-CSR算法的單層胞元結構的周邊模式將會失效而產生一定數量的丟包，而 3D-EEMCR將通過多層胞元結構協作路由來繼續傳遞數據包，所以其平均能耗較高；由于3D-GPR算法遇到局部最小節點就選擇丟包，所以其平均能耗最低。在圖7(b)中，網絡的節點密度較大，幾乎所有消息包均可通過貪婪模式進行傳遞，所以3種算法的平均能耗基本相同。在圖7(c)中， 3D-EEMCR和3D-CSR將定期選取胞父節點且消息包均可通過貪婪模式進行傳遞。3D-EEMCR算法選舉位置更合適的節點作為胞父節點，根據式(2)，其在傳遞消息包時的單跳能耗最低，故其平均能耗最低；而3D-CSR算法比3D-GPR算法需額外消耗能量用于胞父選舉，故其平均能耗最高。

圖5 多通道逆時針法則

圖6 3D-EEMCR, 3D-CSR和3D-GPR發送率對比

圖7 3D-EEMCR, 3D-CSR和3D-GPR平均能耗對比

3D-EEMCR, 3D-GPR和3D-CSR 3種算法的節點存活率隨時間的變化曲線對比如圖8所示。在圖8(a)，圖8(b)和圖8(c)中，由于3D-EEMCR和3D-CSR具有自適應選舉機制來動態地平衡能耗，所以其節點的存活率比3D-GPR高，且隨著胞元內節點數目N的增加，效果越來越明顯；同3D-CSR算法相比，在選取胞父節點時，3D-EEMCR不僅考慮到節點的剩余能量，還將節點的位置信息作為參考量，故其節點的存活率更高。

5 結束語

圖8 3D-EEMCR, 3D-CSR和3D-GPR存活率對比

本文提出的 3D-EEMCR算法采用了主通道和輔助通道相互協助的周邊路由模式，依據主通道優先和輔助通道距離優先等法則，有效地提高了消息包的發送率；同時，該算法提出的自適應胞父選舉機制權衡考慮了節點的剩余能量和位置因素，從而較好地實現了整個網絡的能量均衡，降低了每輪的能量損耗，延長了整個網絡的生命周期。仿真結果驗證了 3D-EEMCR算法的正確性，并表明其比3D-CSR和3D-GPR更具優勢。

[1] Losilla F, Garcia-Sanchez A J, García-Sánchez F, et al.. On the role of wireless sensor networks in intelligent transportation systems[C]. Transparent Optical Networks(ICTON), Coventry, UK, 2012: 1-4.

[2] Hussain R, Sahgal J L, Mishra P, et al.. Application of WSN in rural development, agriculture water management[J].International Journal of Soft Computing and Engineering(IJSCE), 2012, 2(5): 2231-2307.

[3] Lanjwar Namita and Nitnaware Dhiraj. Performance analysis of routing protocols for battlefield monitoring system[J].International Journal of Scientific Engineering and Technology, 2012, 1(2): 55-58.

[4] Goyal D and Tripathy M R. Routing protocols in wireless sensor networks: a survey[C]. Advanced Computing ＆amp;Communication Technologies (ACCT), Rohtak, Haryana,2012: 474-480.

[5] 余勇昌, 韋崗. 無線傳感器網絡路由協議研究進展及發展趨勢[J]. 計算機應用研究, 2008, 25(6): 1616-1621.Yu Yong-chang and Wei Gang. Survey on routing protocols for wireless sensor networks[J]. Application Research of Computers, 2008, 25(6): 1616-1621.

[6] Rahman M A, Anwar F, Naeem J, et al.. A simulation based performance comparison of routing protocol on mobile Ad-hoc network (proactive, reactive and hybrid)[C].International Conference on Computer and Communication Engineering(ICCCE 2010), Kuala Lumpur, Malaysia, 2010:11-13.

[7] Fin G. Routing and addressing problems in large metropolitan-scale internetworks[R]. Technical Report ISU/RR-87-180,USC ISI, Marinadel Ray, California, 1987.

[8] Choi Moonshik and Choo Hyunseung. Bypassing hole scheme using observer packets for geographic routing in WSNs[C].ICOIN 2011, Barcelona, Spain, Jan 26-28, 2011: 435-440.

[9] Khaled D, Bassel A, Abderezak T, et al.. A 3D grid position-based routing protocol for mobile Ad-hoc networks[C]. Proceedings of the International Conference on Computer and Communication Engineering, Kuala, Lumpur,2008: 151-156.

[10] 王紹青, 聶景楠. 無線傳感器網絡中增加協作傳輸及其能量效率研究[J]. 電子與信息學報, 2010, 32(3): 759-762.Wang Shao-qing and Nie Jing-nan. Research on incremental cooperation transmission and its energy efficiency in wireless sensor networks[J]. Journal of Electronics ＆amp; Information Technology, 2010, 32(3): 759-762.

[11] 柯濤, 孫暉, 劉俊延. 基于三維胞元空間的無線傳感器路由算法[J]. 電子與信息學報, 2013, 35(6): 1298-1304.Ke Tao, Sun Hui, and Liu Jun-yan. A wireless sensor network routing algorithm based on 3D cell space[J]. Journal of Electronics ＆amp; Information Technology, 2013, 35(6):1298-1304.

[12] Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks[C]. System Sciences, Maui,Hawaii, Jan. 4-7, 2000: 1-10.