基于稀疏Ad hoc網絡環境的鏈路預補償算法研究

摘 要:著重研究在通信鏈路易中斷的稀疏Ad hoc網絡環境中的數據傳輸問題。提出了鏈路預補償算法，首先給出了關鍵節點的定義與探測算法，然后給出了功率補償算法，通過增大補償節點的功率，增強關鍵節點周圍的連接度，進而提高數據的接收率和吞吐量;并且在NS2模擬器中，對該算法搭建仿真平臺進行了性能評估。仿真結果表明，鏈路預補償算法能夠提高網絡的吞吐量和數據接收率。

關鍵詞:稀疏;Ad hoc網絡;鏈路預補償;接力路由

中圖分類號:TP393 文獻標志碼:A

文章編號:1001-3695(2010)03-1095-04

doi:10.3969/j.issn.1001-3695.2010.03.080

Research on links precompensation algorithm in sparse Ad hoc networks

CHEN Chun-mei， JIANG Hong， LIU Lei

(School of Information Engineering， Southwest Uuiversity of Science Technology， Mianyang Sichuan 621010， China)

Abstract:The research focuses on communication problem in sparse Ad hoc networks where links easily disrupt.This paper presented links precompensation.Firstly gave the definition of critical nodes and the method to detect them，then proposed power control compensation algorithm， through improving nodes’ power to improve the network connectivity and eliminate the impact of the critical node. In the NS2 simulator，designed simulation platform for the scheme.The results show that the links precompensation algorithm can improve network throughput and data delivery ratio.

Key words:sparse; Ad hoc networks; links precompensation; relay routing

稀疏Ad hoc網絡由于節點密度相對較低，無線通信范圍有限，節點間易出現間歇性連接，網絡經常出現分割。傳統的路由協議在尋找不到源端與目的端的路由時，數據將被丟棄，所以不適合稀疏Ad hoc網絡環境。

節點的移動性、稀疏性、能量限制容易導致網絡分割。確保整個網絡的連通性，不僅需要復雜的控制算法，且很難實現，在稀疏的環境中幾乎是不可能的。因此本文提出了提高網絡局部連通性的鏈路預補償算法。首先定義了關鍵節點，然后設計了關鍵節點探測算法和預補償算法，并給出在NS2模擬器中算法的仿真實現結果與分析。

1 關鍵節點定義

應用于連通、密集型Ad hoc網絡中的關鍵節點被定義為由于此節點的失效會導致網絡分割成兩個或更多部分的節點，這種關鍵節點是全局關鍵節點。而對于稀疏Ad hoc網絡，由于網絡拓撲可能已經呈現分割狀態，尋找這種全局性的關鍵節點意義不大。因此本文定義的關鍵節點是局部關鍵節點，這些關鍵節點的失效將導致其周圍某些鄰居節點間不能相互通信，鄰居節點可以是一跳鄰居也可以是兩跳鄰居。關鍵節點的定義如下:如果節點a的鄰節點間沒有本機的中轉就無法互相通信，則說明節點a不能缺少，此時節點a是關鍵節點;如果節點a的鄰節點間可以互相通信，則說明即使節點a出現障礙也不影響其他鄰節點間的通信，此時節點a不是關鍵節點。

如圖1中，左邊區域與右邊區域已經分割，左邊區域節點A、B、C和D中的任何一個節點失效都不會影響到其他節點間的通信，所以左邊區域所有的節點都不是關鍵節點。如果去掉節點H及其相關聯的通信鏈路，其四個鄰居節點J、I、G、F之間就不能互相通信，說明節點H的影響很大，地位很“關鍵”，此時H是關鍵節點。相反，如果節點L失效，其鄰居節點I和M仍然能夠通過H、J、K互相通信，所以節點L失效與否對其他節點的通信沒有影響，節點L不是關鍵節點。

2 關鍵節點探測算法

依據關鍵節點的定義對關鍵節點進行探測。通過在節點與其鄰居節點間交互探測消息來計算是否為關鍵節點，通過鄰居節點間傳送同一個數據包來統計鄰居節點間的通信鏈路。節點隨機選擇其一個鄰居節點，命令此鄰居節點向所有其他鄰居節點發送一個統計包，并要求收到此統計包的鄰居節點發送應答消息，依據收到的應答消息個數與發送的統計包的個數(即鄰居節點的個數減1)比值η來比較鄰居節點間的鏈路連接狀況。

網絡中每個節點獨立發起關鍵節點探測算法，算法是分布式的。考慮盡量減少探測消息對網絡負荷的影響，節點并不是連續發起查找，而是周期性發送探測消息。

關鍵節點探測算法定義了search_keynode_pkt1、search_keynode_pkt2和search_keynode_pkt3三個探測消息類型。其中，search_keynode_pkt1為節點發起探測的命令消息;search_keynode_pkt2為統計包;search_keynode_pkt3為應答消息。關鍵節點查找算法工作原理如圖2所示。

以圖2為例，關鍵節點探測算法步驟如下:

a)以0節點為例，node0查找本機的鄰居列表，若其鄰居節點的個數大于1，則繼續執行，如果沒有鄰居節點，說明此節點是一個孤立節點，只有一個鄰居節點也不符合判斷的條件。

b)node0有六個鄰居節點，隨機選擇其中一個鄰居節點node1，并向其發送search_keynode_pkt1探測消息。此消息包括node0的鄰居節點列表neighbor_list、鄰居節點的個數nbnum、本機的地址Ip0addr。

c)node1接收到search_keynode_pkt1消息后，在本機的路由表中刪除到node0的路由，這樣向node0的鄰居節點發送的數據包就不會通過node0轉發。

d)向node0的所有鄰居節點發送search_keynode_pkt2消息，此消息包括node0鄰居節點的個數nbnum、node0的地址Ip0addr、node1的地址Ip1addr。

e)例如node2是node0和node1的鄰居，那么node2將會收到search_keynode_pkt2的消息，然后node2發送給node0一個確認消息search_keynode_pkt3。此消息的目的地址由收到的search_keynode_pkt2中拷貝，包括search_keynode_pkt2消息中的node1地址、node0的nbnum。

f)node0根據接收到的search_keynode_pkt3消息的個數與本機的nbnum相比較，如果大于η(η值可調)，則說明是關鍵節點，即若node0失效，則有大于(1-η)%鄰節點間不能通信;如果小于η，說明node0的鄰居節點不需要自己的中轉，大于η%的鄰居節點間也能互相發送數據，node0不是一個關鍵節點。η的值可以根據具體的應用環境和性能指標進行相應調解和設置。

關鍵節點探測算法的流程圖如圖3所示。

3 補償節點選擇

可以從兩個方面對關鍵節點進行補償:a)從節點的移動控制方面，可以讓某個節點移動到關鍵節點的位置，以防關鍵節點出現故障帶來的影響;b)可以考慮增大其某個鄰居節點的發射功率，從而覆蓋關鍵節點的通信區域，這樣就解除了關鍵節點的影響。第一種方法需要設置額外節點，對于節點稀疏的環境不符合實際。所以，本文選擇第二種方法，通過增大發射功率覆蓋關鍵節點的通信區域來提高關鍵節點周圍的連通性，消除關鍵節點的影響，即便關鍵節點失效，也不會對其他鄰居節點間的通信造成影響。

補償節點的選擇要綜合考慮補償節點自身的能力和盡可能降低補償關鍵節點對其他節點造成的影響。主要考慮以下幾個因素:

a)增大相同的功率，可以使關鍵節點周圍的連接度增幅最大。補償節點在關鍵節點的鄰居節點中選取距離關鍵節點最近的鄰居節點，覆蓋關鍵節點的通信區域需要增加的傳輸功率最小。

b)作為補償的節點本身的剩余能量。如果節點本身剩余能量有限，為其他節點補償則會加速節點能量的消耗，此節點的失效可能會造成新的鏈路中斷。

c)補償節點也是關鍵節點。如果節點本身是關鍵節點，本身的地位就很關鍵，需要受到保護，也不易作為補償節點。

d)增大功率對其他節點的影響。由前面對功率控制的影響分析可知，增大傳輸功率可能會對其他節點間的通信造成干擾，降低信道的利用率。但是針對節點稀疏、節點間距離較遠的情況，增大傳輸功率對其他節點間的通信一般不會造成影響。

e)不同的補償周期補償節點的選擇。如果一個關鍵節點其“關鍵”地位持續幾個探測周期，每次選擇同一個補償節點是不合理的，這樣會使得補償節點的能量過快消耗。所以，在本次補償周期選擇的補償節點，在下一個補償周期不能再被選，應該選擇距離次近的鄰居節點。通過這樣輪流為關鍵節點補償，均衡消耗各節點能量。

綜合以上因素，補償節點選擇流程如圖4所示。

在圖5中，假設節點A是一個關鍵節點，其無線信號傳輸半徑為r，此時節點B距離A最近，假設同時B符合上述所有條件， B被選為補償節點。節點B增大自己的傳輸半徑為d+r(d為補償節點與關鍵節點之間的距離)，這樣，節點B就覆蓋了節點A的通信區域，節點A的失效就不會對其他鄰居節點的通信造成影響。

4 補償算法

補償算法定義三種數據類型:距離請求消息(location request message)、距離應答消息(location reply message)和補償請求(compensation request)。前兩種消息用于確定補償節點，第三種消息用于通知補償節點具體的補償值。

a)距離計算。利用分組內攜帶的發射信息和物理層反饋的接收信息，由式(1)計算兩節點之間的距離。

Pr=Pt[λ/(4πd)]βGtGr(1)

其中:Pr為接收功率;Pt為發送功率;λ為載波波長;d為源節點和目的節點間的距離;Gt為發射機天線增益;Gr為接收機天線增益。β取決于無線傳播模型，對于TwoRayGround雙徑地面反射，β=4。

b)補償請求。當節點判斷自己是關鍵節點時，如果其能量即將耗盡，或者出現某種故障即將退出網絡，則發起補償算法，請求其他節點的補償。

補償算法的具體步驟如下:

(a)當節點判斷自己是關鍵節點時，如果需要補償，首先關鍵節點發送location_request message消息給其所有的鄰節點，以尋找距離自己最近的鄰居節點。

(b)鄰節點收到此分組后，如果其本身不是關鍵節點、剩余能量滿足條件，并且在上一個周期不是補償節點，計算與關鍵節點之間的距離，將此值寫入location_reply消息，發送至關鍵節點，如果不滿足條件則不回應消息。

(c)關鍵節點收到應答消息后，選擇距離最近的鄰居節點，并發送包含具體功率增加的信息，功率增加后補償節點的通信半徑為兩點之間的距離d加上關鍵節點的通信半徑r。

(d)補償節點根據式(1)計算新的發射功率，根據關鍵節點的狀況調整發射功率。

(e)功率增加后，不能讓補償節點長期保持大功率的發射，節點輪流補償。

5 仿真結果及分析

仿真實驗主要比較擴展補償算法的OLSR協議和傳統OLSR協議在稀疏Ad hoc網絡環境中的通信性能，從而確定補償算法是否能有效改善稀疏Ad hoc網絡性能。

選擇數據接收率、網絡吞吐量、能量消耗幾個參數作為比較的指標。

節點的移動性會導致網絡拓撲不斷改變，網絡中的關鍵節點也會隨之改變，所以有必要周期性地對關鍵節點進行查找。查找周期過長，就無法跟蹤網絡拓撲的改變，關鍵節點不能及時得到補償;查找周期過短，則會增大網絡的開銷。因此合理地選擇查找周期是很有必要的。

5.1 查找周期對補償算法的影響

a)仿真環境。仿真場景為1 000 m×1 000 m稀疏節點環境，關鍵節點探測周期分別為5 s、10 s、15 s、20 s、25 s;仿真時間為100 s;節點無線傳輸半徑為200 m;仿真節點數為30;節點的運動速度將在(1，5)m/s內隨機選擇;節點停留時間為1 s;設置η為20%。

b)數據流設置。采用CBR(常速數據流)數據流，通信源隨機設置20個，每個數據源持續發送總時間為5 s。設定發送速率為每秒兩個數據包，數據包長為1 024 Byte。

選擇數據接收率和路由開銷作為比較的兩個性能指標。路由開銷是平均每發送一個應用層數據包需要發送多少路由層的控制分組，即所有發送的路由層數據總和與應用層數據總和之比。

如圖6所示，隨著探測周期由5 s增大到25 s，數據接收率由55%下降至25%，補償算法的作用很低，路由開銷由30降低至15。探測周期為10 s時的路由開銷比5 s時的基本降低一半左右，而數據接收率僅降低了10%左右。探測周期在10~25 s之間時，路由開銷下降不明顯，而數據接收率反而下降很快。探測周期的大小對網絡性能有很大影響，綜合考慮數據接收率和路由開銷兩個指標，在中低速環境中，探測周期選擇在10 s左右，既能保證數據的接收率，也不會過重增加網絡的負荷。

5.2 不同移動速率下的吞吐量和接收率比較

a)仿真環境。仿真場景為1 000 m×1 000 m稀疏節點環境，關鍵節點探測周期為10 s;仿真時間為100 s;節點無線傳輸半徑為200 m;仿真節點數為30;節點的運動速度分別將在(0，1)m/s、(1，5)m/s、(5，10)m/s、(10，15)m/s、(15，20)m/s、(20，25)m/s、(25，30)m/s、(30，35)m/s、(35，40)m/s中隨機選擇;節點停留時間為1 s。

b)數據流量。為了直接考察路由性能，采用CBR，通信源設置為20個，設定發送速率為每秒兩個數據包，數據包長為1 024 Byte。網絡中的數據量最大為40 KBps，接近于實際工作中的Ad hoc網絡的流量負載。

c)仿真過程。為了對比補償算法對網絡性能的影響，在探測到關鍵節點后，令關鍵節點失效一短暫時間，然后恢復正常。每一次運行NS模擬器都會導入一個節點運動場景文件和流量生成文件。為了盡可能地實現仿真的可靠性，對于每一組結果數據，都要求采用不同的運動場景仿真10次，然后求平均值。總共生成180個運動場景文件，需要運行180次仿真過程。

d)結果分析。仿真結果如圖7所示，擴展了補償算法的協議在數據接收率和吞吐量上比傳統OLSR路由協議提高了一倍左右;隨著節點運動速度的增加，補償算法的優勢逐漸減弱，并且，網絡在低速的環境中數據接收率也僅能達到50%左右。分析原因如下:

(a)節點的運動速度加快，導致網絡的拓撲結構急劇變化。關鍵節點也在很快地改變，補償算法跟不上網絡結構的變化，可能剛補償的關鍵節點很快不再是關鍵節點，這樣補償算法就不能發揮優勢。考慮到補償算法帶來的控制消息的增加，查找周期不能設置得太小。在中低速的環境中，如1～5 m/s，在每一個查找周期內，節點移動的最大距離僅在10～50 m，相對于200 m的無線傳輸半徑，節點的移動不會使網絡的拓撲產生急劇的變化，所以補償算法在中低速的環境中能很好地改善網絡的性能。

(b)用setdest工具生成的是稀疏的隨機分布模型，網絡拓撲初始化時并不一定是一個全連通的網絡，補償算法只能改善局部的網絡性能，對于已經產生分割的網絡區域不起作用。所以對于隨機移動模型，在稀疏環境中，網絡的吞吐量和接收率比較低。

5.3 補償前后能耗的比較

本實驗模擬一個小型網絡，具體分析節點移動對網絡拓撲和補償算法能耗影響。

仿真環境為500 m×500 m仿真區域，5個移動節點，仿真時間為50 s，節點的移動速度在(0，2)m/s范圍內隨機選擇，查找周期為10 s，選擇在AODV路由協議上擴展補償算法。實驗結果如圖8、9所示。

由圖8(a)中可以看出，節點0為網絡中的關鍵節點，[1~4]號節點為節點0的鄰居節點，節點2與3、1與2的通信都需要節點0的中轉，所以節點0的失效會造成整個網絡通信中斷。由于節點的運動速度較低，網絡的拓撲變化不大，30 s后拓撲基本不變。如果關鍵節點即將失效則發起補償請求，節點1距離節點0最近，為73 m，同時節點1不是關鍵節點，其剩余能量也滿足條件，所以選擇節點1為補償節點，增大節點1的傳輸功率對關鍵節點補償，并由式(1)計算出節點1新的傳輸功率為0.978 1 W。10 s時，節點0仍然是關鍵節點，根據補償節點選擇依據，在這個補償周期選擇次近的節點4作為補償節點，同時節點1的發射功率恢復到原值;20 s時，節點1距離節點0已經很近，節點2與3、1與2的通信可以通過節點1的中轉，節點0不再是關鍵節點，因此20 s后不需要再補償。

由圖9可以看出，補償后網絡中整體能量消耗略有增加，但是相差不大。影響能耗的主要因素是發送數據分組的多少和傳輸功率的大小。傳輸功率增加，相應地增加了節點能量的消耗。但是在關鍵節點失效后，由于AODV路由協議是按需式路由，源節點和目的節點之間沒有通信路由時，源節點發送路由查找請求分組、等待應答、超時重傳，這些控制分組相應地增加了網絡的能耗;補償算法不是采取連續補償，也節省了網絡的能耗。所以網絡的整體能耗相差不大，功率補償算法并沒有使得網絡的整體能耗增大很多。

6 結束語

本文給出了關鍵節點的定義，即關鍵節點是網絡某局部區域中的關鍵節點，并不是整個網絡的關鍵節點。網絡中的關鍵節點是重點維護的對象，它的失效會造成網絡中某些節點通信的中斷。提出了鏈路預補償算法來預防關鍵節點失效所造成的影響，并對該算法的仿真結果進行了分析，補償算法在中低速環境中可以有效地改善稀疏Ad hoc網絡的性能，提高數據的接收率和吞吐量;通過對模擬環境中節點運動的詳細分析，表明功率補償對網絡的能耗影響很小，并分析了其原因。補償算法簡單，容易實現，可以有效提高稀疏Ad hoc網絡的性能。

參考文獻:

[1]

WISITPONGPHAN N，BAI Fan，MUDALIGE P，et al.On the routing problem in disconnected vehicular Ad hoc network[C]//Proc of the 26th IEEE International Conference on Computer Communications.2007:327-339.

[2]CHAKERES I D，BELDING-ROYER E M.AODV routing protocol implementation design[C]//Proc of the 24th International Conference on Distributed Computing Systems Workshops.2004:698-703.

[3]JOHNSON D B，MALTZ D A，HU Y C.Dynamic source routing protocol for mobile Ad hoc network(DSR)[R/OL].(2003-04-16).http://www.cs.cmu.edu/~dmaltz/internet-drafts/draft-ietf-manet-dsr-09.txt.

[4]AISSANI M，SENOUCI M R，DEMIGNA W，et al.Optimizations and performance study of the dynamic source routing protocol[C]//Proc of the 3rd International Conference on Networking and Services.Washington DC:IEEE Computer Society，2007:107-116.

[5]ZHAO W，AMMAR M，ZEGURA E.A message ferrying approach for data delivery in sparse mobile Ad hoc networks[C]//Proc of the 5th ACM International Symposium on Mobile Ad hoc Networking and Computing.New York:ACM Press，2004:187-198.

[6]王永勝，吳德偉，劉勇.基于NS2網絡仿真研究[J].計算機仿真，2004，21(11):257-259.

[7]于斌，孫斌.NS2與網絡模擬[M].北京:人民郵電出版社，2006.

[8]LI Qun，RUS D.Communication in disconnected Ad hoc networks using message relay[J].Journal of Parallel and Distributed Computing，2003，63(1):75-86.

[9]FALL K.A delay-tolerant networking architecture for challenged Internets[C]//Proc of Conference on Applications，Technologies，Architectures and Protocols for Computer Communications.2003:27-34.

[10]JAIN S，FALL K，PATRA R.Routing in a delay tolerant networking[C]//Proc of Conference on Applications，Technologies，Architectures and Protocols for Computer Communications.2004:145-158.