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

劉俊延 孫 暉柯 濤 路 揚(yáng)

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

1 引言

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

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

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

2 算法模型

2.1 網(wǎng)絡(luò)模型

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

圖1 3維胞元空間模型

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

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

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

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

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

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

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

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

圖2 消息包傳遞法則

2.2 節(jié)點(diǎn)能耗模型

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

3 3D-EEMCR算法

3.1 自適應(yīng)胞父選舉機(jī)制

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

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

3.2 胞元路由機(jī)制

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

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

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

圖3 胞父選舉流程圖

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

圖4 主通道胞元層選定

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

3.2.2 多通道逆時(shí)針法則 多通道逆時(shí)針法則的一般過程：

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

4.2 仿真結(jié)果分析

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

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

圖5 多通道逆時(shí)針法則

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

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

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

5 結(jié)束語(yǔ)

圖8 3D-EEMCR, 3D-CSR和3D-GPR存活率對(duì)比

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

[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)絡(luò)路由協(xié)議研究進(jìn)展及發(fā)展趨勢(shì)[J]. 計(jì)算機(jī)應(yīng)用研究, 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)絡(luò)中增加協(xié)作傳輸及其能量效率研究[J]. 電子與信息學(xué)報(bào), 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]. 電子與信息學(xué)報(bào), 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.