Ad Hoc網(wǎng)絡(luò)中基于能量耗費(fèi)和阻塞成本路由算法研究①

許 鵬

(合肥職業(yè)技術(shù)學(xué)院,安徽 合肥 230013)

0 引 言

無(wú)線Ad hoc網(wǎng)絡(luò)是一種全部由無(wú)線裝置構(gòu)建的，無(wú)需任何基礎(chǔ)架構(gòu)，每個(gè)節(jié)點(diǎn)可隨意移動(dòng)并有發(fā)送和接收信息的裝置，節(jié)點(diǎn)之間的所有通信都是通過(guò)相鄰節(jié)點(diǎn)互相傳遞、交換信息實(shí)現(xiàn)。在無(wú)線ad hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)在處理運(yùn)算、操作系統(tǒng)待機(jī)或傳送數(shù)據(jù)時(shí)，都會(huì)消耗一定的電量，而這些無(wú)線裝置通常用電池來(lái)提供能量，所以減少電源消耗至關(guān)重要。傳統(tǒng)的路由選擇協(xié)議(如：AODV、DSR)[1]都是選擇最小跳數(shù)路徑，并未考慮到電源消耗，如果選擇的路徑中有某個(gè)節(jié)點(diǎn)電量快要用完，將會(huì)造成網(wǎng)絡(luò)分割，使得數(shù)據(jù)無(wú)法傳送到目的節(jié)點(diǎn)，同時(shí)由于網(wǎng)絡(luò)擁塞也會(huì)對(duì)能量消耗產(chǎn)生比較大的影響，因此需要設(shè)計(jì)一種減少能量消耗和阻塞成本的路由算法來(lái)有效延長(zhǎng)電池的壽命來(lái)提升網(wǎng)絡(luò)的吞吐量。

1 相關(guān)技術(shù)

1.1 AODV路由協(xié)議

AODV路由協(xié)議是反應(yīng)式路由協(xié)議[3]。源節(jié)點(diǎn)想傳送數(shù)據(jù)給某個(gè)目的節(jié)點(diǎn)，若路由表中尚無(wú)任何記錄時(shí)，則啟動(dòng)路由發(fā)現(xiàn)程序去查找一條可達(dá)路徑，并廣播RREQ封包給相鄰的節(jié)點(diǎn)，接收到此封包的節(jié)點(diǎn)會(huì)去比對(duì)其路由表中是否已經(jīng)存在可達(dá)路徑，若有，則比較其路由表中的目的端順序號(hào)是否比RREQ中的目的端順序號(hào)的值大，若較大或相等，但跳數(shù)較小，則單播一個(gè)路由應(yīng)答封包至反向路徑；若較小，必須把RREQ廣播給下游的鄰近節(jié)點(diǎn)。依此類(lèi)推，直到到達(dá)目的節(jié)點(diǎn)。

在轉(zhuǎn)送RREQ的過(guò)程中，每個(gè)節(jié)點(diǎn)會(huì)自動(dòng)地設(shè)定反向路徑。收到RREQ的中間節(jié)點(diǎn)會(huì)判斷是從那一個(gè)相鄰的節(jié)點(diǎn)收到的，并將此相鄰節(jié)點(diǎn)的IP地址記錄到自己的路由表里，并把跳數(shù)值加一，接著轉(zhuǎn)送給下一個(gè)鄰近節(jié)點(diǎn)，下一個(gè)鄰近節(jié)點(diǎn)重復(fù)同樣的步驟。在RREP反向回傳到源節(jié)點(diǎn)的過(guò)程中，此路徑上的每個(gè)節(jié)點(diǎn)都會(huì)設(shè)定一個(gè)轉(zhuǎn)送指針，指向送來(lái)RREP的節(jié)點(diǎn)，并在路由表中更新此路由的時(shí)延。

1.2 PSR路由算法

節(jié)省能源路由算法一直是無(wú)線ad hoc網(wǎng)絡(luò)研究的熱點(diǎn)，Chai Keong Toh提出最小總傳輸功率路由(MTPR)[4]，在按需路由協(xié)議基礎(chǔ)上考慮到電源因素。在傳送數(shù)據(jù)前，計(jì)算每個(gè)節(jié)點(diǎn)的電量消耗，找出耗電量最少的路徑來(lái)傳送數(shù)據(jù)。缺點(diǎn)是當(dāng)節(jié)點(diǎn)電量相同時(shí)，可能因?yàn)槟硞€(gè)節(jié)點(diǎn)傳送功率較大，耗電量也較大，將導(dǎo)致路徑失效數(shù)據(jù)無(wú)法傳送。而最小電池成本路由(MBCR)[5]是計(jì)算路徑上每一節(jié)點(diǎn)所剩余的電量，找出一條總剩余電量最多的路徑來(lái)傳送數(shù)據(jù)。其缺點(diǎn)是路徑中可能存在某些節(jié)點(diǎn)的電量不足，導(dǎo)致路徑失效數(shù)據(jù)無(wú)法傳送。

Singh等提出功率感知源路由(PSR)[6]，該方法與MBCR類(lèi)似，不同之處在于PSR加入傳送一個(gè)數(shù)據(jù)報(bào)文所消耗的電量大小、電量之間的比值及權(quán)重因子作為計(jì)算能量消耗的方式。缺點(diǎn)是將數(shù)據(jù)報(bào)文所消耗的電量大小設(shè)為常數(shù)，并非與傳送功率或節(jié)點(diǎn)間距離有關(guān)，而且此方法只考慮剩余電量大小，并未考慮造成電量消耗快慢的因素，因此可能會(huì)找到剩余電量最大但電量消耗較快的路由。

1.3 Dijkstra 算法

Dijkstra 算法[7]是用來(lái)找出從單一節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑的方法。首先以來(lái)源節(jié)點(diǎn)作始發(fā)節(jié)點(diǎn)，從相連且尚未被選定節(jié)點(diǎn)中，選定離來(lái)源節(jié)點(diǎn)距離最短的節(jié)點(diǎn)，并及時(shí)更新加入節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離，通過(guò)此方法不斷添加新的節(jié)點(diǎn)，直到所有的節(jié)點(diǎn)都被加入為止，即可求得最短路徑。AODV、DSR路由協(xié)議在選擇路徑時(shí)也運(yùn)用Dijkstra算法來(lái)求各節(jié)點(diǎn)之間的最短路徑。

2 路由算法設(shè)計(jì)

將傳統(tǒng)ad hoc網(wǎng)絡(luò)中的AODV路由協(xié)議加入能量花費(fèi)以及隊(duì)列長(zhǎng)度作為選擇路徑的依據(jù)，設(shè)計(jì)一種最小能量和阻塞成本路由算法(Minimum Energy and Jam Cost Routing，MEJCR)，利用這種算法可以找到花費(fèi)能量最少的路由，從而有效延長(zhǎng)電池的壽命。

在一般的路由協(xié)議中，通常只考慮傳送功率Pt對(duì)能量成本的影響，但能量成本并非只與傳送功率Pt有關(guān)，也與電子電路功率Pec有關(guān)。取Pec=15mW，則傳送功率的大小與距離d有密切關(guān)系，如下式所示：

Ebit=Pt×Tbit+Pec×Tbit

(1)

Pt=Pr×dL

(2)

(3)

其中Rs為符率，以baud為單位；Pr為接受功率；L為路徑損失指數(shù)；Ebit為單位能量消耗，b為每一符號(hào)的位數(shù)，與所用的調(diào)變方法有關(guān)。圖1為常見(jiàn)的Rs和b所得到的Tbit值：

圖1 常見(jiàn)的Tbit值

通過(guò)選擇Rs和b值可將能量成本最小化，這里取Rs=1Msymbols/sec,b=2bits/symbols，則可將Ebit表示為：

Ebit=(0.5PrdL+7.5)nJ

(4)

路徑損失指數(shù)L的值通常介于2～5之間，同時(shí)考慮到路徑擁塞所造成的能量成本提升，需要加入避免擁塞的條件。當(dāng)d=25m時(shí)，Pr=13nW，可以構(gòu)建以下能量成本模型：

Cjk=

(5)

其中djk代表節(jié)點(diǎn)j與節(jié)點(diǎn)k之間的距離，Cjk為從節(jié)點(diǎn)j到節(jié)點(diǎn)k所需花費(fèi)的能量，Q代表隊(duì)列的大小，其值通常為0～10之間，Qthreshold為擁塞程度的臨界值，、β，y為加權(quán)因子。在公式(5)中，前面部分為不考慮擁塞對(duì)于能量成本的影響，后面部分則是把隊(duì)列長(zhǎng)度作為擁塞程度的指標(biāo)，而Qthreshold則作為擁塞嚴(yán)重程度的判別，當(dāng)目前的隊(duì)列大于Qthreshold值時(shí)，則表示擁塞程度較高，其所得到的能量成本值，相對(duì)于隊(duì)列長(zhǎng)度小于Qthreshold值時(shí)為大。

路徑的能量成本為路徑中各連接的能量成本總和，令(j,k)代表連接節(jié)點(diǎn)j與k的連接，s與d分別代表來(lái)源節(jié)點(diǎn)與目的節(jié)點(diǎn)，∏(s,d)為s到d之所有路徑所成集合，π(s,d)∈∏(s,d)為s到d的一條路徑，則π(s,d)的能量成本Cπ(s,d)可表示為：

(6)

最后從中選出一條花費(fèi)成本為最小的路徑R：

(7)

3 路由選擇

通常一個(gè)ad hoc網(wǎng)絡(luò)可被表示成一個(gè)圖形的方式G=(V,E)，V(G)代表節(jié)點(diǎn)的集合，E(G)代表所有連接兩個(gè)節(jié)點(diǎn)所形成的鏈路集合。假設(shè)每個(gè)節(jié)點(diǎn)的最大涵蓋范圍都相同，當(dāng)E(G)中存在一條鏈路(j,k)，則節(jié)點(diǎn)j、k必須都在彼此的涵蓋范圍內(nèi)。MEJCR構(gòu)建在AODV路由協(xié)議之上，其選擇路徑時(shí)也與AODV路由協(xié)議一樣運(yùn)用到Dijkstra 算法來(lái)求各節(jié)點(diǎn)之間的最短路徑。其路由原理為，當(dāng)來(lái)源節(jié)點(diǎn)有數(shù)據(jù)要傳給目的節(jié)點(diǎn)時(shí)，會(huì)先查看自己路由表中是否有路徑可直接到達(dá)目的節(jié)點(diǎn)，若有，則利用此路徑傳送數(shù)據(jù)；若沒(méi)有，則利用廣播RREQ封包來(lái)找尋路徑。當(dāng)中間節(jié)點(diǎn)收到此報(bào)文時(shí)，會(huì)依據(jù)與前一個(gè)節(jié)點(diǎn)的距離以及目前隊(duì)列長(zhǎng)度的大小，來(lái)得到個(gè)別的鏈路成本，并將此連接成本加到RREQ報(bào)文的header上面，傳往下一個(gè)節(jié)點(diǎn)，當(dāng)下一個(gè)節(jié)點(diǎn)收到此RREQ報(bào)文時(shí)，將自己所計(jì)算出來(lái)的鏈路成本累加到RREQ封包的header上，依此類(lèi)推，直到目的節(jié)點(diǎn)收到此RREQ封包為止。目的節(jié)點(diǎn)會(huì)從所有可能路徑中挑選出一條總鏈路成本最小的作為回傳RREP封包及傳送數(shù)據(jù)封包的路徑。

舉例說(shuō)明如下：如圖2所示，連線上的數(shù)字代表兩節(jié)點(diǎn)之間的距離，而隊(duì)列圖標(biāo)里的數(shù)字表示目前隊(duì)列的長(zhǎng)度，當(dāng)來(lái)源節(jié)點(diǎn)S有數(shù)據(jù)要傳給目的節(jié)點(diǎn)D時(shí)， AODV路由協(xié)議選擇路徑是依據(jù)最小跳數(shù)，故選擇S→3→D為傳送數(shù)據(jù)路徑，其每比特能量消耗為924nj。PSR路由協(xié)議以縮短節(jié)點(diǎn)之間距離為選擇依據(jù)，其路徑為s→1→2→3→5→d，每比特能量消耗為664nj，而MEJCR會(huì)在所有可能的路徑中，選擇隊(duì)列長(zhǎng)度總和最少的路徑來(lái)做傳送，其選擇路徑為s→1→3→4→d，其每比特能量消耗為最少的374nJ。

圖2 路徑的建立

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

利用模擬仿真實(shí)驗(yàn)來(lái)評(píng)估MEJCR算法，并且分別與AODV和PSR算法做比較。以下首先介紹實(shí)驗(yàn)?zāi)M環(huán)境以及效能指標(biāo)，接著對(duì)模擬結(jié)果加以分析。

4.1 實(shí)驗(yàn)環(huán)境設(shè)定

模擬環(huán)境設(shè)定及結(jié)果分析主要是采用VC++語(yǔ)言編寫(xiě)，分別在100×100、150×150、200×200、250×250、300×300m2區(qū)域范圍內(nèi)分布30個(gè)節(jié)點(diǎn)以及在100×100、200×200、300×300、400×400、500×500m2區(qū)域范圍內(nèi)分布50個(gè)節(jié)點(diǎn)，以探討不同密度對(duì)于找尋路徑所花費(fèi)成本的影響。以同樣數(shù)量的節(jié)點(diǎn)而言，分布范圍越大，則節(jié)點(diǎn)密度越小。為提高實(shí)驗(yàn)結(jié)果的可信度，對(duì)每一種分布范圍與節(jié)點(diǎn)數(shù)的組合，分別利用隨機(jī)數(shù)生成100個(gè)不同的網(wǎng)絡(luò)拓?fù)?，而每一?jié)點(diǎn)的隊(duì)列長(zhǎng)度也以隨機(jī)數(shù)生成，其值介于0與10之間，最后結(jié)果以不同網(wǎng)絡(luò)拓?fù)渌玫钠骄当硎尽Ｔ贛EJCR中選擇Qthreshold=7,β=2,γ=1。為簡(jiǎn)化仿真，假設(shè)網(wǎng)絡(luò)中各節(jié)點(diǎn)的剩余電量與初始電量相同，用PSR法選擇路徑時(shí)，兩者比值可忽略不計(jì)，其路徑選擇只需考慮距離因素。

使用三種效能指標(biāo)來(lái)評(píng)估各種不同路由算法的優(yōu)劣：(1)數(shù)據(jù)封包沿著各路由算法所選擇路徑所花費(fèi)能量的比較；(2)省電率比較；(3)平均各節(jié)點(diǎn)擁塞程度比較。

4.2 結(jié)果分析

下圖分別顯示節(jié)點(diǎn)數(shù)為30和50的靜態(tài)網(wǎng)絡(luò)下，不同網(wǎng)絡(luò)拓?fù)浞秶腥N不同算法每比特能量消耗的模擬結(jié)果。由此可見(jiàn)，MEJCR不論在網(wǎng)絡(luò)拓?fù)浞秶』虼髸r(shí)，相較于其他兩種方法所得到的每比特能量消耗都小，原因在于其選擇路徑時(shí)既考慮縮短鏈路的距離又考慮到網(wǎng)絡(luò)擁塞造成的影響。圖3、圖4的差別是在其他條件相同的情況下，50個(gè)節(jié)點(diǎn)所花費(fèi)的能量比30個(gè)節(jié)點(diǎn)少，原因在于50節(jié)點(diǎn)之間聯(lián)機(jī)機(jī)率高，因此花費(fèi)就小。

圖3 30個(gè)節(jié)點(diǎn)的能量花費(fèi)

圖4 50個(gè)節(jié)點(diǎn)的能量花費(fèi)

同時(shí)考慮到節(jié)省電源因素，將MEJCR所選出來(lái)的路徑中各節(jié)點(diǎn)間的鏈路成本相加，再分別與AODV和PSR法做比較，其計(jì)算方式如下：

(8)

(9)

其中Cπ(s,d)(MEJCR|PSR|AODV)代表各種不同方法所選出來(lái)路徑能量消耗總和。

圖5、圖6中顯示，MEJCR算法相對(duì)于AODV、PSR算法都較省電，省電率為的53%(圖5)以及51%(圖6)。

圖5 30個(gè)節(jié)點(diǎn)省電率

圖6 50個(gè)節(jié)點(diǎn)省電率

圖7,圖8顯示每個(gè)節(jié)點(diǎn)在不同方法中所得到的平均隊(duì)列長(zhǎng)度(與擁塞程度正關(guān)聯(lián))，MEJCR法比其他兩種方法所得到的隊(duì)列長(zhǎng)度都小很多，介于2～4之間，因此能量花費(fèi)也最少。其他兩種方法所得到的平均隊(duì)列長(zhǎng)度差異不大，介于4～6之間。經(jīng)能量成本模型計(jì)算后，AODV法由于本身所選的路徑其節(jié)點(diǎn)之間的距離較遠(yuǎn)，而隊(duì)列長(zhǎng)度又不比其他方法小，因此其能量花費(fèi)也最高。

圖7 30個(gè)節(jié)點(diǎn)的平均擁塞程度

圖8 50個(gè)節(jié)點(diǎn)的平均擁塞程度

5 結(jié) 論

將ad hoc網(wǎng)絡(luò)中的傳統(tǒng)的路由選擇算法加以修改，設(shè)計(jì)一種新的有效節(jié)省電源的路由選擇算法最小能量和阻塞成本路由算法，其選擇路徑的依據(jù)不但考慮最小能量消耗的問(wèn)題，也進(jìn)一步考慮擁塞對(duì)于能量消耗的影響。通過(guò)實(shí)驗(yàn)結(jié)果分析比較可知，這種方法可以有效減少電源消耗，同時(shí)也能夠有效避免擁塞現(xiàn)象發(fā)生。