許 鵬

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

0 引 言

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

1 相關技術

1.1 AODV路由協(xié)議

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

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

1.2 PSR路由算法

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

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

1.3 Dijkstra 算法

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

2 路由算法設計

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

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

Ebit=Pt×Tbit+Pec×Tbit

(1)

Pt=Pr×dL

(2)

(3)

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

圖1 常見的Tbit值

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

Ebit=(0.5PrdL+7.5)nJ

(4)

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

Cjk=

(5)

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

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

(6)

最后從中選出一條花費成本為最小的路徑R：

(7)

3 路由選擇

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

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

圖2 路徑的建立

4 仿真實驗

利用模擬仿真實驗來評估MEJCR算法，并且分別與AODV和PSR算法做比較。以下首先介紹實驗模擬環(huán)境以及效能指標，接著對模擬結(jié)果加以分析。

4.1 實驗環(huán)境設定

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

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

4.2 結(jié)果分析

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

圖3 30個節(jié)點的能量花費

圖4 50個節(jié)點的能量花費

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

(8)

(9)

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

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

圖5 30個節(jié)點省電率

圖6 50個節(jié)點省電率

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

圖7 30個節(jié)點的平均擁塞程度

圖8 50個節(jié)點的平均擁塞程度

5 結(jié) 論

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