基于能耗均衡的Mesh網(wǎng)絡(luò)路由算法設(shè)計(jì)

王娜娜(山西警察學(xué)院，山西太原 030032)

基于能耗均衡的Mesh網(wǎng)絡(luò)路由算法設(shè)計(jì)

王娜娜
(山西警察學(xué)院，山西太原 030032)

為了提高M(jìn)esh網(wǎng)絡(luò)用戶的使用感知，防止終端節(jié)點(diǎn)能量耗盡而導(dǎo)致的路由重選,本文提出同時(shí)考慮網(wǎng)絡(luò)節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)之間的距離和節(jié)點(diǎn)剩余能量的路由方法，來(lái)均衡網(wǎng)絡(luò)的能量，讓能量剩余過(guò)少的節(jié)點(diǎn)和離網(wǎng)關(guān)過(guò)遠(yuǎn)的節(jié)點(diǎn)盡量避免中轉(zhuǎn)數(shù)據(jù)，以此來(lái)平衡對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)能量均衡與數(shù)據(jù)傳輸效率的要求。通過(guò)實(shí)驗(yàn)與RM-AODV和OTR算法進(jìn)行對(duì)比表明，基于能耗均衡的Mesh網(wǎng)絡(luò)路由算法，在總體能耗和數(shù)據(jù)延遲上都要優(yōu)于RM-AODV和OTR，達(dá)到了很好的能耗均衡效果。

Mesh網(wǎng)絡(luò)；能量均衡；路由；網(wǎng)絡(luò)壽命

無(wú)線Mesh網(wǎng)絡(luò)是一種多跳的、具有自組織和自愈特點(diǎn)的寬帶無(wú)線網(wǎng)絡(luò)結(jié)構(gòu)，它通常是一個(gè)高帶寬和高速率的網(wǎng)絡(luò)。無(wú)線Mesh網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。無(wú)線Mesh網(wǎng)絡(luò)在現(xiàn)實(shí)中得到了廣泛的應(yīng)用，它可以有多種應(yīng)用，包括室內(nèi)寬帶網(wǎng)、社區(qū)鄰域網(wǎng)、企業(yè)網(wǎng)、樓房自治網(wǎng)等。無(wú)線Mesh網(wǎng)絡(luò)的每一個(gè)節(jié)點(diǎn)都能自我管理。但路由中某個(gè)節(jié)點(diǎn)若作為路由節(jié)點(diǎn)，由于頻繁的路由轉(zhuǎn)發(fā)，就會(huì)過(guò)早地耗盡該節(jié)點(diǎn)的能量，使經(jīng)過(guò)該節(jié)點(diǎn)的路徑需要重新發(fā)現(xiàn)和選擇。

圖1 Mesh網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

針對(duì)無(wú)線Mesh網(wǎng)絡(luò)應(yīng)用中的問(wèn)題，已經(jīng)有很多研究者做出非常有效的優(yōu)化改進(jìn)。李旭[1]提出一種無(wú)線Mesh網(wǎng)絡(luò)自適應(yīng)路由緩存更新算法，該算法可以將網(wǎng)絡(luò)中的斷鏈信息及時(shí)地?cái)U(kuò)散到受斷鏈影響的相關(guān)節(jié)點(diǎn)進(jìn)行路由緩存的動(dòng)態(tài)更新；沈小建[2]提出了一種無(wú)線Mesh網(wǎng)絡(luò)中編碼感知且負(fù)載均衡的多播路由協(xié)議，該協(xié)議可以增加網(wǎng)絡(luò)編碼機(jī)會(huì)，同時(shí)考慮到網(wǎng)絡(luò)中的負(fù)載均衡；石文孝[3]提出一種無(wú)線Mesh網(wǎng)絡(luò)干擾與區(qū)域負(fù)載感知路由度量，通過(guò)平均競(jìng)爭(zhēng)度描述干擾鏈路對(duì)同一信道的競(jìng)爭(zhēng)程度和干擾鏈路負(fù)載的離散程度來(lái)衡量網(wǎng)絡(luò)負(fù)載分布狀況。上述這些算法都取得了很好的優(yōu)化效果，但這些算法考慮的因素都比較單一，沒(méi)有同時(shí)考慮終端節(jié)點(diǎn)的能量和離網(wǎng)關(guān)節(jié)點(diǎn)的距離。本文算法在網(wǎng)絡(luò)能量均衡和網(wǎng)絡(luò)穩(wěn)定性上均好于常用的RM-AODV和OTR算法。

1 Mesh網(wǎng)絡(luò)能耗模型

1.1 Mesh網(wǎng)絡(luò)模型及問(wèn)題

為了研究Mesh網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)據(jù)傳輸能耗，現(xiàn)用數(shù)學(xué)方法建立如下Mesh網(wǎng)絡(luò)模型。我們用一個(gè)無(wú)向圖G(V,E)來(lái)描述一個(gè)Mesh無(wú)線網(wǎng)絡(luò)，其中V為Mesh網(wǎng)絡(luò)節(jié)點(diǎn)集合，任意節(jié)點(diǎn)v∈V，由于節(jié)點(diǎn)v因?yàn)楣β实南拗疲衅涮囟ǖ膫鬏斁嚯x，在這個(gè)傳輸距離范圍內(nèi)的節(jié)點(diǎn)稱為節(jié)點(diǎn)v的鄰近節(jié)點(diǎn)。鄰近節(jié)點(diǎn)集合為L(zhǎng)(v)，集合L(v)內(nèi)的節(jié)點(diǎn)均可雙向相互通信。對(duì)于任意節(jié)點(diǎn)u∈L(v)，節(jié)點(diǎn)v和節(jié)點(diǎn)u之間存在一條雙向通信鏈路evu，evu∈E。

整個(gè)Mesh無(wú)線網(wǎng)絡(luò)數(shù)據(jù)的傳輸，就是節(jié)點(diǎn)在其鄰近節(jié)點(diǎn)集合下一跳的選擇。這個(gè)下一跳的選擇有很多種，其中最常用的就是選擇鄰近節(jié)點(diǎn)集合中離網(wǎng)關(guān)節(jié)點(diǎn)最近的那個(gè)節(jié)點(diǎn)為下一跳。即若節(jié)點(diǎn)v的鄰近節(jié)點(diǎn)集合L(v)內(nèi)，存在一個(gè)節(jié)點(diǎn)k∈L(v)，Lc(k)為節(jié)點(diǎn)k到網(wǎng)關(guān)節(jié)點(diǎn)的距離。若對(duì)任意v′∈L(v)，v′≠v，v′≠k，有Lc(k)≤Lc(v′)，則節(jié)點(diǎn)k為節(jié)點(diǎn)v數(shù)據(jù)傳輸?shù)南乱惶?jié)點(diǎn)。

如上所述的選擇下一跳節(jié)點(diǎn)方式，最大的好處是可以讓數(shù)據(jù)以最短距離鏈路來(lái)傳輸，提高數(shù)據(jù)傳輸?shù)乃俾?。但是在一個(gè)局部范圍鄰域內(nèi)的節(jié)點(diǎn)會(huì)選擇同一條鏈路傳輸數(shù)據(jù)，這樣數(shù)據(jù)鏈路上的節(jié)點(diǎn)就會(huì)頻繁地傳輸數(shù)據(jù)，導(dǎo)致節(jié)點(diǎn)的能量過(guò)早耗盡。這將會(huì)導(dǎo)致經(jīng)過(guò)該節(jié)點(diǎn)的路徑需要重新發(fā)現(xiàn)和選擇，從而增加了大量的路由時(shí)間和因節(jié)點(diǎn)失效而造成的重路由時(shí)間。

1.2 能耗模型建立

IEEE802.11s協(xié)議中將Mesh網(wǎng)絡(luò)節(jié)點(diǎn)功率模式定義為三種，分別是：

Active模式：此模式為未開啟功率節(jié)省功能模式。這時(shí)節(jié)點(diǎn)將用額定最大功率來(lái)進(jìn)行數(shù)據(jù)發(fā)射，非常消耗節(jié)點(diǎn)的能量。

LS模式：此模式為開啟功率節(jié)省功能模式。Mesh節(jié)點(diǎn)將對(duì)鄰近節(jié)點(diǎn)集合內(nèi)節(jié)點(diǎn)的Beacon幀進(jìn)行監(jiān)聽。

DS模式：此模式為開啟功率節(jié)省功能模式。此模式下STA節(jié)點(diǎn)將不監(jiān)聽鄰近節(jié)點(diǎn)集合內(nèi)節(jié)點(diǎn)的Beacon幀。

設(shè)節(jié)點(diǎn)Active模式、LS模式、DS模式對(duì)應(yīng)的能耗分別為Eactive、Els、Eds，每種模式下發(fā)送的幀的數(shù)量分別為Qactive、Qls、Qds，平均每幀發(fā)送耗時(shí)為tactive、tls、tds，這個(gè)耗時(shí)是一個(gè)平均值；節(jié)點(diǎn)的發(fā)射功率為Pnode，α，β為L(zhǎng)S模式和DS模式的節(jié)能占比率，常數(shù)C為受環(huán)境影響導(dǎo)致的能耗，則有如下能耗計(jì)算公式：

Eactive=Pnode×tactive×Qactive+C.

(1)

Els=α×Pnode×tls×Qls+C.

(2)

Eds=β×Pnode×tds×Qds+C.

(3)

則節(jié)點(diǎn)的總的數(shù)據(jù)發(fā)射功耗EC為：

EC=Eactive+Els+Eds.

(4)

設(shè)節(jié)點(diǎn)自身電路的功耗為Eele，則節(jié)點(diǎn)總的功耗Etotal為：

Etotal=EC+Eele.

(5)

2 基于區(qū)域能耗均衡的Mesh路由算法

2.1 下一跳節(jié)點(diǎn)選擇

通過(guò)以上分析，得知常用的Mesh路由方法，通過(guò)考慮鄰近節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)之間的距離遠(yuǎn)近來(lái)考慮鏈路下一跳節(jié)點(diǎn)，這樣容易導(dǎo)致某些節(jié)點(diǎn)的能量過(guò)早耗盡。本文同時(shí)考慮節(jié)點(diǎn)與網(wǎng)關(guān)距離及節(jié)點(diǎn)所剩能量?jī)蓚€(gè)因素，來(lái)選擇路由鏈路的下一跳節(jié)點(diǎn)。

如圖2所示，假設(shè)圖中G為網(wǎng)關(guān)節(jié)點(diǎn)，e為當(dāng)前需要轉(zhuǎn)發(fā)數(shù)據(jù)的Mesh節(jié)點(diǎn)，以節(jié)點(diǎn)e為中心，半徑r范圍內(nèi)有n個(gè)鄰近節(jié)點(diǎn){n1,n2,…,nn}，這n個(gè)節(jié)點(diǎn)所攜帶的能量為{e1,e2,…,en}，每個(gè)節(jié)點(diǎn)到網(wǎng)關(guān)節(jié)點(diǎn)G的距離分別為{d1,d2,…,dn}，設(shè)下一跳節(jié)點(diǎn)選擇的參考參數(shù)為pen，pen的計(jì)算如下：

pen=δ·en+μ·dn.

(6)

nnext=max{pe1,pe2,…,pen}.

(7)

其中，δ為節(jié)點(diǎn)能量的參考比例系數(shù)，μ為節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)之間距離的參考比例系數(shù)，則下一跳節(jié)點(diǎn)nnext為選擇參考參數(shù)pen值的最大節(jié)點(diǎn)。

2.2 數(shù)據(jù)傳輸鏈路分析

如圖3所示，實(shí)線鏈路為本文算法的數(shù)據(jù)鏈路，虛線為常用算法的數(shù)據(jù)鏈路，虛線的圓圈為數(shù)據(jù)發(fā)送節(jié)點(diǎn)的鄰近節(jié)點(diǎn)集合。本文方法在開始總體的鏈路距離上要比傳統(tǒng)的方法遠(yuǎn)一些，但是這是網(wǎng)絡(luò)里沒(méi)有出現(xiàn)節(jié)點(diǎn)失效的情況下，傳統(tǒng)方法中，當(dāng)網(wǎng)絡(luò)出現(xiàn)節(jié)點(diǎn)失效的時(shí)候，有的鏈路就會(huì)很不穩(wěn)定，傳輸距離會(huì)很曲折，也會(huì)比本文的算法的鏈路更遠(yuǎn)。

圖2 下一跳節(jié)點(diǎn)選擇示意圖

圖3 優(yōu)化后數(shù)據(jù)傳輸鏈路示意圖

本文方法中鄰近節(jié)點(diǎn)集合的半徑選擇，要根據(jù)實(shí)際情況來(lái)設(shè)定，半徑越大就會(huì)在單次傳輸數(shù)據(jù)的時(shí)候考慮的節(jié)點(diǎn)更多，但也會(huì)增加計(jì)算量，加大數(shù)據(jù)傳輸延遲。如果半徑太小，就會(huì)導(dǎo)致考慮的節(jié)點(diǎn)太少，能量均衡的效果就不明顯。所以要經(jīng)過(guò)驗(yàn)證選擇一個(gè)符合要求的半徑。

2.3 優(yōu)化Mesh路由算法實(shí)現(xiàn)

Type mesh_routing_function()//優(yōu)化Mesh路由算法。

{

If(star_first)//當(dāng)首次啟動(dòng)網(wǎng)絡(luò)時(shí)，初始化網(wǎng)絡(luò)。

{

Mesh_Init();//初始化網(wǎng)絡(luò)。

}

If(！r)//如果半徑r！=0。

}

Search_node();//搜索半徑為r范圍內(nèi)的鄰近節(jié)點(diǎn)。

For(k=1;k

{

Pe_node(n)；//計(jì)算每個(gè)鄰近節(jié)點(diǎn)的pe值。

}

Max_pe_transmission(data，nnext)；//求pe值最大的節(jié)點(diǎn)，并轉(zhuǎn)發(fā)數(shù)據(jù)。

}

Else Transmission(data，nnext);//直接傳輸數(shù)據(jù)給下一跳節(jié)點(diǎn)。

}

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)采用的工具是MATLAB7.0，實(shí)驗(yàn)中，假設(shè)在1000×1000區(qū)域內(nèi)分布了81個(gè)傳感器節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都攜帶單位電量1J，每個(gè)節(jié)點(diǎn)地位均等。

為了驗(yàn)證本文的路由算法的能耗均衡性和網(wǎng)絡(luò)穩(wěn)定性，本文將與常用的RM-AODV和OTR算法進(jìn)行對(duì)比。具體算法對(duì)比實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

圖4 網(wǎng)絡(luò)剩余終端對(duì)比

圖5 數(shù)據(jù)延遲對(duì)比

圖4為本文算法與RM-AODV和OTR算法在使用同樣時(shí)間內(nèi)剩余節(jié)點(diǎn)終端的數(shù)量的對(duì)比圖。隨著使用時(shí)間的增加，三種算法的網(wǎng)絡(luò)中剩余終端節(jié)點(diǎn)的數(shù)量越來(lái)越少，但本文算法剩余的終端要多于其他兩種算法，說(shuō)明能耗要低于其他兩種算法，所以剩余節(jié)點(diǎn)要比其他兩種多。圖5為本文算法與RM-AODV和OTR算法的數(shù)據(jù)發(fā)送延遲對(duì)比圖。隨著發(fā)送數(shù)據(jù)量的增加，三種算法的數(shù)據(jù)延遲都在增加，但本文算法的數(shù)據(jù)延遲要低于其他兩種算法，說(shuō)明本文算法沒(méi)有降低數(shù)據(jù)傳輸?shù)男省?/p>

4 結(jié)語(yǔ)

無(wú)線Mesh網(wǎng)絡(luò)是非常常用的無(wú)線網(wǎng)絡(luò)之一，由于它自身需要攜帶電源來(lái)發(fā)送數(shù)據(jù)，往往會(huì)因?yàn)楣?jié)點(diǎn)能量耗盡而失效，從而造成某些終端失效，增加了大量的路由時(shí)間和因節(jié)點(diǎn)失效而造成的重路由時(shí)間。本文通過(guò)在鄰近節(jié)點(diǎn)集合范圍內(nèi)考慮下一跳節(jié)點(diǎn)的能量來(lái)實(shí)現(xiàn)Mesh網(wǎng)絡(luò)的能量均衡，本文的方法同時(shí)考慮了節(jié)點(diǎn)的能耗和節(jié)點(diǎn)到網(wǎng)關(guān)的距離，平衡網(wǎng)絡(luò)能量均衡和數(shù)據(jù)傳輸效率。通過(guò)實(shí)驗(yàn)表明，本文Mesh網(wǎng)絡(luò)路由算法要比常用的RM-AODV和OTR算法，在總體能耗和數(shù)據(jù)延遲方面均有很大的改進(jìn)和提高。

[1]李旭,宋顧楊,劉穎.無(wú)線Mesh網(wǎng)絡(luò)自適應(yīng)路由緩存更新算法[J].北京交通大學(xué)學(xué)報(bào),2015(5):112-116.

[2]沈小建,陳志剛,劉立.無(wú)線Mesh網(wǎng)絡(luò)中編碼感知且負(fù)載均衡的多播路由[J].通信學(xué)報(bào),2015(4):78-83.

[3]石文孝,許銀龍,王繼紅,等.無(wú)線Mesh網(wǎng)絡(luò)干擾與區(qū)域負(fù)載感知路由度量[J].北京郵電大學(xué)學(xué)報(bào),2014(5):76-81.

[4]Helber Silva,Aldri Santos,Michele Nogueira.Routing management for performance and security tradeoff in wireless mesh networks[J].International Journal of Information Security,2015(1):33-38.

[5]Jin Wang,Kejie Lu,Shukui Zhang,et al.An efficient communication relay placement algorithm for content-centric wireless meshnetworks[J].Int.J.Commun.Syst.2015(2):55-61.

[6]吳文甲,楊明,羅軍舟.無(wú)線Mesh網(wǎng)絡(luò)中滿足帶寬需求的路由器部署方法[J].計(jì)算機(jī)學(xué)報(bào),2014(2):88-94.

[7]杜瑞穎,陳晶,何琨,等.基于博弈的無(wú)線Mesh網(wǎng)絡(luò)高效可靠路由算法[J].北京交通大學(xué)學(xué)報(bào),2013(5):211-216.

[8]Xiaoyuan Guo,Feng Wang,Jiangchuan Liu,et al.Path diversified multi-QoS optimization in multi-channel wireless mesh networks[J].Wireless Networks,2014(6):11-16.

[9]Di Wu,Shih-Hsien Yang,Lichun Bao,et al.Joint multi-radio multi-channel assignment,scheduling and routing in wireless mesh networks[J].Wireless Networks,2014(1):23-28.

[10]鄧曉衡,劉強(qiáng),李旭,等.鏈路質(zhì)量與負(fù)載敏感的無(wú)線Mesh網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2013(10):67-73.

Mesh Network Routing Algorithm Based on Energy Consumption Balance

WANG Na-na

(Shanxi Police College, Taiyuan Shanxi 030032,China)

In order to improve the perception of Mesh network users, and prevent the terminal node energy depletion caused by the rerouting. Considering routing method between network node and gateway node distance and node residual energy, to balance the network energy, and let node residual energy too little to avoid data transfer, so far from the gateway node to avoid transfer data to the network node energy balance and data transmission efficiency of the flat heng. Compared with RM-AODV and OTR algorithm, the results show that Mesh network routing algorithm based on energy consumption balance, the overall energy consumption and delay data are better than those of the RM-AODV and OTR.

Mesh network; energy consumption balance; routing; network lifetime

2016-11-10

王娜娜(1980- )，女，講師，碩士，從事虛擬現(xiàn)實(shí)技術(shù)應(yīng)用以及網(wǎng)絡(luò)信息安全和管理研究。

TP301.6

A

2095-7602(2017)06-0028-05