陸 偉，楊余旺

(1.南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 江蘇 南京 210094；2.淮陰師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 江蘇 淮安 223300)

0 引 言

移動Ad Hoc網(wǎng)絡(luò)(mobile Ad Hoc network，MANET)是一種無任何基礎(chǔ)架構(gòu)的開放式、可擴(kuò)展式自組織網(wǎng)絡(luò)。由于MANET節(jié)點(diǎn)具有轉(zhuǎn)發(fā)功能，其接收數(shù)據(jù)分組和轉(zhuǎn)發(fā)均需要消耗能量。與源節(jié)點(diǎn)和目的節(jié)點(diǎn)不同，中間節(jié)點(diǎn)需要消耗更多的能量維持正常通信和網(wǎng)絡(luò)連通性[1]。

目前，MANET中已經(jīng)有針對節(jié)能路由協(xié)議的研究文獻(xiàn)，這些協(xié)議均是將功率控制引入到現(xiàn)有各種路由協(xié)議設(shè)計(jì)之中[2-9]。文獻(xiàn)[4]提出了一種旨在增強(qiáng)網(wǎng)絡(luò)壽命的能量感知路由協(xié)議框架，和DSR協(xié)議相比，改進(jìn)協(xié)議能夠節(jié)省20%的能量。文獻(xiàn)[6]使用圖論理論形成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以確保節(jié)點(diǎn)最小能量消耗維持網(wǎng)絡(luò)連通性，但研究結(jié)果并未從能量和時(shí)間上進(jìn)行理論分析及測試。文獻(xiàn)[8]提出了一種能量感知多徑路由協(xié)議AOMR-LM，能夠平衡各條支路上的能量消耗和保存節(jié)點(diǎn)剩余能量，其使用了一種能量感知機(jī)制，通過節(jié)點(diǎn)的能量水平選擇節(jié)點(diǎn)剩余能量并實(shí)現(xiàn)路徑分類，和其它節(jié)能路由相比能夠有效提高網(wǎng)絡(luò)壽命、節(jié)約能耗。從上述研究可以發(fā)現(xiàn)，大多節(jié)能路由協(xié)議是基于最短路徑算法改進(jìn)，而最短路徑路由中存在的缺陷會同樣存在于改進(jìn)算法之中，缺乏創(chuàng)新性，存在缺少數(shù)學(xué)解析模型的理論基礎(chǔ)。綜上所述，由于已有的節(jié)能路由協(xié)議并未分析出路由尋路效率與能量消耗之間的關(guān)系，因此普遍存在節(jié)能效率低下的問題。

為此，本文引入MANET信號屬性，在其基礎(chǔ)上建立簡單穩(wěn)健的數(shù)學(xué)解析模型，提出了一種能同時(shí)解決能量和路由效率的節(jié)能路由協(xié)議(energy saving routing protocol based on mathematical modeling，ESRP-MM)，最后實(shí)驗(yàn)結(jié)果驗(yàn)證了ESRP-MM的優(yōu)越性。

1 問題描述

現(xiàn)有大多數(shù)路由協(xié)議[10]均使用最短路徑尋優(yōu)技術(shù)，但最短路徑尋優(yōu)存在的問題不可忽視，因?yàn)槠鋬H考慮了最短傳輸距離和時(shí)間，并未將干擾、衰落、散射、噪聲等因素考慮其中。此外，最短路徑尋優(yōu)技術(shù)容易造成網(wǎng)絡(luò)分割中斷，這是因?yàn)橐苿庸?jié)點(diǎn)耗盡能量后可能中斷路徑重啟路由發(fā)現(xiàn)過程。再者，將能耗問題和最短路徑聯(lián)合考慮，將會進(jìn)一步重新定義最短路徑的有效性，因?yàn)槠渎窂匠杀竞陀?jì)算復(fù)雜度將會因?yàn)槟芎囊蛩氐囊攵鬄榻档汀?/p>

經(jīng)典AODV協(xié)議[11]是當(dāng)前MANET節(jié)能路由改造中最常用的基礎(chǔ)協(xié)議，盡管AODV具有低延時(shí)和按需建立路由等優(yōu)點(diǎn)，但其仍存在各種不足使得其能量節(jié)省效率難以大幅降低。比如，在大規(guī)模高密度MANET網(wǎng)絡(luò)環(huán)境下，AODV會產(chǎn)生不一致的路由從而增加重傳次數(shù)，從而造成了不必要的能量消耗。

因此，針對上述問題，需要從數(shù)學(xué)模型建立角度設(shè)計(jì)路由規(guī)則。在能量控制階段，應(yīng)該在隨機(jī)鏈路選擇或者路由維持的基礎(chǔ)上考慮設(shè)計(jì)路由策略，節(jié)能策略應(yīng)該從路由發(fā)現(xiàn)過程就開始執(zhí)行，故下文將設(shè)計(jì)一種節(jié)能路由協(xié)議。

2 ESRP-MM協(xié)議的設(shè)計(jì)

本節(jié)提出了適用于大規(guī)模MANET網(wǎng)絡(luò)的節(jié)能路由協(xié)議ESRP-MM，引入了帶寬效率到協(xié)議中，提高了節(jié)能效率和通信性能。為提高計(jì)算效率，ESRP-MM使用了成本因素用于選擇源目的節(jié)點(diǎn)對之間的最佳路由。其次，在路由發(fā)現(xiàn)階段通過更精確的成本計(jì)算實(shí)現(xiàn)最低能量路由選擇。ESRP-MM協(xié)議運(yùn)行在802.11MAC協(xié)議[12]之上。

2.1 能量模型

能量模型設(shè)計(jì)基于MAC層協(xié)議，目前MAC媒體接入控制協(xié)議分為點(diǎn)協(xié)調(diào)式接入機(jī)制和分布式協(xié)調(diào)接入機(jī)制，由于點(diǎn)協(xié)調(diào)式接入機(jī)制是集中式控制，故ESRP-MM使用分布式協(xié)議接入機(jī)制。因此，當(dāng)移動節(jié)點(diǎn)想要發(fā)送數(shù)據(jù)給另一個(gè)節(jié)點(diǎn)時(shí)，通常要進(jìn)行網(wǎng)絡(luò)分配向量初始檢查。如果發(fā)現(xiàn)網(wǎng)絡(luò)分配向量大于0，節(jié)點(diǎn)停止發(fā)送直至其為0。為了消除MANET隱藏終端[13]的影響，ESRP-MM使用CMRTS和CMCTS兩類不同類型的控制分組。源節(jié)點(diǎn)發(fā)送CMRTS給接收節(jié)點(diǎn)，當(dāng)接收節(jié)點(diǎn)收到CMRTS后，目的節(jié)點(diǎn)發(fā)送CMCTS分組。如果發(fā)送節(jié)點(diǎn)在特定時(shí)間周期內(nèi)沒有收到CMCTS，則重新發(fā)送。源節(jié)點(diǎn)收到CMCTS后，將發(fā)送數(shù)據(jù)分組，而接收節(jié)點(diǎn)收到數(shù)據(jù)分組后將返回確認(rèn)分組。此過程一至重復(fù)到源節(jié)點(diǎn)收到接收節(jié)點(diǎn)返回的確認(rèn)分組為止。圖1給出了ESRP-MM狀態(tài)轉(zhuǎn)移圖。

圖1 ESRP-MM分組發(fā)送狀態(tài)轉(zhuǎn)移

(1)

式中：ηo為物理層的開銷。因此，結(jié)合概率理論和上述能量模型，ESRP-MM協(xié)議中，數(shù)據(jù)分組發(fā)送需要的累積能量表示為

(2)

式中：Em表示MAC層消耗能量。此外，數(shù)據(jù)分組成功接收消耗能量為

(3)

式中：在源節(jié)點(diǎn)i和目的節(jié)點(diǎn)j之間，ESRP-MM認(rèn)為有(n-1)個(gè)中間節(jié)點(diǎn)。0,1,2…,M為節(jié)點(diǎn)序列號。結(jié)合式(2)、式(3)，有數(shù)據(jù)分組傳輸需要消耗系統(tǒng)的累積能量表達(dá)式為

(4)

2.2 路由成本評估

由前文可知，傳輸過程中大多數(shù)參數(shù)是較容易計(jì)算的，但也存在一些參數(shù)不容易得到。ESRP-MM協(xié)議考慮信號衰減由節(jié)點(diǎn)的隨意移動性引起，衰減速率可被定義為1/DP，其中D為節(jié)點(diǎn)間距離，P為路徑損耗指數(shù)[14]。因此，數(shù)據(jù)分組接收能量水平Er取決于發(fā)射端能量Et和DP比值，其中Et為分組傳輸所需的能量，故有表達(dá)式為

(5)

式中：α是實(shí)時(shí)環(huán)境中和環(huán)境因素相關(guān)的變量參數(shù)。因此，移動節(jié)點(diǎn)可以根據(jù)已知數(shù)據(jù)分組的接收能量水平以及期望接收能量值預(yù)估出其它數(shù)據(jù)分組傳輸需要的能量。此外，數(shù)據(jù)分組中的比特錯誤通常由噪聲、干擾和沖突造成，802.11MAC使用載波偵聽能夠有效識別沖突和干擾。因此，在利用噪聲和干擾參數(shù)的基礎(chǔ)上，ESRP-MM能夠通過調(diào)制方案和接收能量水平預(yù)估出誤碼率。如果分組包含s個(gè)比特，誤碼率為BER，則有分組錯誤率為1-(1-BER)s。因此，很容易給出RTS、CTS、ACK等控制分組的分組錯誤率，分組錯誤率主要受分組大小、干擾、接收能量和噪聲等因素影響。不過，RTS控制分組的分組錯誤率僅受沖突和干擾兩個(gè)因素影響，結(jié)合式(1)，將無線環(huán)境中的噪聲干擾表示為eIN，沖突為eCL，故有RTS請求控制分組的分組錯誤率為

eR,i,j=eIN+eCL-eINeCL

(6)

2.3 能量感知路由

ESRP-MM協(xié)議旨在路由發(fā)現(xiàn)過程中尋找具有高節(jié)能效率的路由，通過周期性維護(hù)路由以減小動態(tài)拓?fù)湓斐傻牟焕绊?。和傳統(tǒng)路由協(xié)議相似，ESRP-MM以尋找最短路徑的方法初始化路由發(fā)現(xiàn)進(jìn)程。以圖2所示的場景為例，在源節(jié)點(diǎn)X和目的節(jié)點(diǎn)Y之間存在3種路徑。考慮到路徑上的所有節(jié)點(diǎn)，最短路徑有XPQY，XRSY，XTUY，而潛在的其它路徑有XPY，XQY，XRY，XSY，XTY和XUY。以S表示收發(fā)X和Y的路徑集合，Ns為路徑s的跳數(shù)，Es,i是路徑s上消耗的能量。因此，最短路徑可表示為

Sp=argmin(Ns),s∈S

(7)

類似，可定義節(jié)能最短路徑為

(8)

圖2 一種簡單MANET場景

ESRP-MM協(xié)議中，設(shè)計(jì)了一種路由策略用于確保首先找到最短路徑再篩選出具有最低能量消耗的路徑。在路由發(fā)現(xiàn)過程中，RREQ包含能量損耗和跳數(shù)等附加信息。源節(jié)點(diǎn)廣播RREQ分組，接收到RREQ的中間節(jié)點(diǎn)更新RREQ中的能量損耗和跳數(shù)信息。此外，ESRP-MM再設(shè)置兩個(gè)條件用于判斷中間節(jié)點(diǎn)是否轉(zhuǎn)發(fā)RREQ：①如果之前未收到相同的RREQ分組；②如果收到的分組和之前分組具有相同的跳數(shù)，但是具有更低的能量損耗。因此，前者可確保最短路徑尋優(yōu)，后者能夠確保能耗最低。

3 性能評估

本節(jié)使用OPNET14.5網(wǎng)絡(luò)仿真軟件對ESRP-MM協(xié)議進(jìn)行了性能仿真，從分組傳輸時(shí)間、分組丟失率、數(shù)據(jù)流丟失數(shù)目、耗能等角度給出了協(xié)議性能評估，并和文獻(xiàn)[8]所提協(xié)議、經(jīng)典協(xié)議AODV進(jìn)行性能對照。由于ESRP-MM借鑒文獻(xiàn)[8]的思想，其仿真環(huán)境、參數(shù)配置相近，而AODV協(xié)議則通過適當(dāng)修改使其能夠計(jì)算能量消耗，并適用于ESRP-MM的仿真環(huán)境。在給定仿真區(qū)域面積內(nèi)，節(jié)點(diǎn)位置隨機(jī)分布，節(jié)點(diǎn)采用隨機(jī)路點(diǎn)移動模型。仿真結(jié)果通過獨(dú)立50次循環(huán)求統(tǒng)計(jì)平均獲得。主要仿真參數(shù)配置見表1。

表1 仿真參數(shù)配置

圖3給出了ESRP-MM協(xié)議在不同分組大小、不同節(jié)點(diǎn)移動速率條件下的分組傳輸時(shí)間仿真結(jié)果。分組傳輸時(shí)間指分組由源節(jié)點(diǎn)發(fā)送經(jīng)中間節(jié)點(diǎn)轉(zhuǎn)發(fā)目的節(jié)點(diǎn)接收整個(gè)過程需要的時(shí)間。由圖3可知，分組傳輸時(shí)間會隨節(jié)點(diǎn)移動速率和分組長度增加而上升。在節(jié)點(diǎn)移動速率小的條件下，分組大小變化對分組傳輸時(shí)間的影響呈正相關(guān)，但影響較小。在節(jié)點(diǎn)移動速率大時(shí)，分組長度越大分組傳輸時(shí)間越長。

圖3 分組大小不同時(shí)的網(wǎng)絡(luò)分組傳輸時(shí)間仿真結(jié)果

圖4給出了分組丟失率隨仿真時(shí)間的變化結(jié)果。和文獻(xiàn)[8]相比，ESRP-MM分組丟失率更小，表明ESRP-MM具有更優(yōu)的分組傳輸性能。

圖4 分組丟失率隨仿真時(shí)間變化趨勢

圖5給出了不同節(jié)點(diǎn)數(shù)目條件下請求分組能量消耗結(jié)果。仿真對網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)發(fā)送的請求分組的能量消耗進(jìn)行統(tǒng)計(jì)并求平均給出單請求分組耗能結(jié)果。據(jù)圖可知，AODV隨著節(jié)點(diǎn)數(shù)目增加其能量消耗近線性增長，故AODV存在網(wǎng)絡(luò)節(jié)點(diǎn)易耗盡能量關(guān)機(jī)的問題，這是因?yàn)榫W(wǎng)絡(luò)規(guī)模的增加會使中間節(jié)點(diǎn)變多進(jìn)而加速中間節(jié)點(diǎn)能量消耗所致。

圖5 節(jié)點(diǎn)數(shù)目不同時(shí)請求信息能量消耗結(jié)果

文獻(xiàn)[8]使用了迭代計(jì)算方法得到節(jié)點(diǎn)剩余能量，由于計(jì)算方法的低復(fù)雜度降低了系統(tǒng)的能量消耗。ESRP-MM由于使用了基于鏈路成本的路由因子，提高了最佳路由尋找速度，此外并未在能量計(jì)算過程中引入額外的復(fù)雜度，故大大降低了尋路能耗。

圖6給出了不同節(jié)點(diǎn)移動速率條件下的單數(shù)據(jù)分組能量消耗結(jié)果。高速移動節(jié)點(diǎn)一般會引起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的急劇變化、路由中斷和隱藏終端等問題。相比AODV和文獻(xiàn)[8]，ESRP-MM的單分組耗能隨著節(jié)點(diǎn)移動速率增加并未快速增加，而是保持在一個(gè)較穩(wěn)定的低能耗水平，這和其使用的能量控制策略有關(guān)。ESRP-MM的能量控制策略能夠有效解決隱藏終端問題，能夠在高速移動場景下縮小給鄰居節(jié)點(diǎn)發(fā)送信息的傳輸范圍從而有效降低發(fā)送功率，實(shí)現(xiàn)單分組傳輸?shù)湍芎牡哪康摹?/p>

圖6 不同節(jié)點(diǎn)移動速率條件下單數(shù)據(jù)分組能耗結(jié)果

4 結(jié)束語

能量節(jié)省問題是移動Ad Hoc網(wǎng)絡(luò)路由協(xié)議的研究點(diǎn)之一，傳統(tǒng)節(jié)能路由協(xié)議大多是在最短路徑路由協(xié)議基礎(chǔ)上增加能量控制策略實(shí)現(xiàn)，普遍存在能量效率低下、缺少數(shù)學(xué)模型論證的問題。本文提出了一種節(jié)能路由協(xié)議ESRP-MM，建立了包含節(jié)點(diǎn)屬性的數(shù)學(xué)模型，將帶寬效率引入到尋路策略中，描述了一種簡單能量控制策略，同時(shí)實(shí)現(xiàn)了最短路徑尋優(yōu)和能量節(jié)約。仿真結(jié)果驗(yàn)證表明ESRP-MM協(xié)議相較傳統(tǒng)協(xié)議具有更優(yōu)的傳輸性能和能量節(jié)約性能。下一步，將借鑒ESRP-MM路由思想，研究適用于無線傳感器網(wǎng)絡(luò)的節(jié)能路由。