劉俊延 孫 暉柯 濤 路 揚

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

1 引言

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

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

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

2 算法模型

2.1 網(wǎng)絡模型

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

圖1 3維胞元空間模型

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

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

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

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

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

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

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

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

圖2 消息包傳遞法則

2.2 節(jié)點能耗模型

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

3 3D-EEMCR算法

3.1 自適應胞父選舉機制

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

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

3.2 胞元路由機制

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

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

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

圖3 胞父選舉流程圖

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

圖4 主通道胞元層選定

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

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

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

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

4 仿真實驗與結果分析

4.1 仿真環(huán)境及參數(shù)設置

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

4.2 仿真結果分析

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

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

圖5 多通道逆時針法則

圖6 3D-EEMCR, 3D-CSR和3D-GPR發(fā)送率對比

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

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

5 結束語

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

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

[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] 余勇昌, 韋崗. 無線傳感器網(wǎng)絡路由協(xié)議研究進展及發(fā)展趨勢[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] 王紹青, 聶景楠. 無線傳感器網(wǎng)絡中增加協(xié)作傳輸及其能量效率研究[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.