Ad hoc網絡鄰居節點表自適應構建與維護算法

摘 要:在Ad hoc網絡貪婪地理路由協議中，傳統的鄰居節點表自適應構建與維護采用周期性信標交換算法，在移動環境下會導致通信暫盲現象。在分析節點移動對網絡連通性影響的基礎上，提出一種基于鏈路斷開概率的自適應信標交換算法來實現鄰居節點表自適應構建與維護。仿真結果表明，該算法不但提高了數據分組傳送成功率，而且還降低了控制開銷，因此該算法適用于移動Ad hoc 網絡。

關鍵詞:Ad hoc網絡; 貪婪地理路由協議; 信標交換算法; 通信暫盲現象

中圖法分類號:TP393; TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2243-03

doi:10.3969/j.issn.1001-3695.2010.06.070

Neighbors table updating algorithm for Ad hoc networks

WEN Wei1， WANG Ling2， ZHANG Hengyang2

(1. Faculty of Information Engineering， Jiangxi University of Science Technology， Ganzhou Jiangxi 341000， China;

2. College of Electronic Science Engineering， National University of Defense Technology， Changsha 410073，China)

Abstract:On the basis of analyzing the phenomenon of temporary communication blindness resulted from fixed period beacon exchange in greedy geographical routing of Ad hoc networks， this paper proposed a new neighbors table updating algorithm. Simulation showes that the adaptive beacon exchange algorithm can acquire high packet success delivery ratio for eliminating the phenomenon of temporary communication blindness， and get low consumption. So the algorithm is scalable and applicable to largescale Ad hoc networks.

Key words: Ad hoc networks; greedy geographical routing; neighbors table updating; temporary communication blindness

0 引 言

對于基于地理位置信息的貪婪地理路由協議[1~4]來說，鄰居節點表的構建與維護作為貪婪轉發策略選擇下一跳節點的依據，是路由協議的基礎。在移動環境下，網絡拓撲不斷發生變化，各個節點的鄰居節點個數和位置也隨之發生變化，需要各個節點不斷進行信標交換，動態地構建和維護各自的鄰居節點表，掌握局部的拓撲信息。目前使用信標交換的路由協議大多采用周期性信標交換算法，研究發現，周期性信標交換算法在移動環境中存在通信暫盲現象[5]，嚴重影響數據傳輸的可靠性。為了克服這種因周期性信標交換算法帶來的問題，有必要設計一種新的鄰居節點表自適應構建與維護算法，以及時地反映鄰居節點的位置變化情況，提高鄰居節點表的構建與維護的準確性及實時性，為下一跳節點的選擇提供可靠的依據。

1 相關工作

由于周期性信標交換的局限性，文獻[6]提出當實際位置與數據庫位置的差值超過所設定的門限值時，便發送信標來更新位置數據庫的方法。文獻[7]中提出一種自適應位置更新策略，結合移動預測和按需學習方法來發送信標，但信標交換沒有區分工作節點和空閑節點。文獻[8]中提出三種信標交換算法:a)基于時間，周期性的信標交換算法，運動快的節點信標發送周期比運動慢的節點短;b)基于距離，節點每移動一定的距離便發送一個信標;c)基于速率，移動速率越快的節點信標發送頻率越高。文獻[9]中也提出與文獻[8]類似的基于距離的信標發送方法，同時還提出了反應式信標交換及事件驅動的信標發送算法，但是這種觸發的反應式信標會涉及到整個網絡，在數據傳送頻繁的網絡中，控制開銷將會大大增加。文獻[10]中提出一種自適應信標交換算法，節點在鏈路斷開之前發送信標，同時使鄰居節點表中相應的鄰居節點過期來達到消除通信暫盲現象的目的。文中所采用的分析是一種極限情況，缺乏理論推導分析。文獻[5]研究指出在統計意義上移出概率與時間存在著一一對應的關系，運行時間越長，鏈路斷開概率越大。

上述算法從不同程度上克服了周期性信標交換算法存在的缺點，但是，這些算法所制定的信標交換周期大多為定性獲得，缺乏數學上的理論推導分析。

2 自適應信標交換算法

節點移動性強的Ad hoc網絡中，信標交換的周期可以設計得比較小;反之，信標交換的周期可以設計得比較大。如果節點發送信標周期設置較小的值，就可以提高節點對鏈路通斷的感知靈敏度，在鏈路即將斷開之前，提前按照貪婪轉發策略重新進行分布式的路由選擇，可以減緩通信暫盲現象。在移動場景確定的條件下，統計意義上，鏈路斷開概率和運行時間具有一一對應的關系，設定一個鏈路斷開概率門限值，則對應于某一條鏈路的運行時間，并以此時間來觸發下一次信標交換。這種方法可以從理論上進行定量分析，并且具有很大的可行性。根據上述原理，本文提出一種基于鏈路斷開概率的自適應信標交換算法:根據網絡系統的QoS要求，設定一個鏈路斷開概率門限值，節點則根據周圍所有鄰居節點的相對狀態動態地計算相對應的平均剩余鏈路壽命值，作為下一次信標交換的周期。基于SGM(smooth GausssemiMarkov)移動模型[11]分析節點移動對網絡連通性能的影響并計算鏈路斷開概率，為網絡信標交換算法提供理論依據。

2.1 鏈路斷開概率的計算

如果在時刻t0，節點1和節點2之間的鏈路已經存在，隨著節點的移動和時間的推進，鏈路斷開的可能性越來越大。在場景確定，節點的通信距離、節點間相對距離確定的情況下，從數學統計意義上，鏈路斷開概率與時間存在一一對應的關系，如果確定一個鏈路斷開概率門限值，則相應地確定了一個時間，并以此作為下一次信標交換的周期。

從文獻[11]中可知，如果將節點的運動時間以時隙Δt進行等分，每一個時隙即為一步，在第k步時節點1和節點2的運動速度分別是v1k和v2k，用vk和ρk分別表示第k步時節點2相對節點1的相對速度和相對距離，如圖1所示，因此有如下表達式

vk=v2k-v1k; ρk=ρk-1+vk(1)

由余弦定理可得

ρk=ρ2k-1+v2k-2ρk-1vkcos θk(2)

θk=arccosρ2k-1+v2k-ρ2k2ρk-1vk(3)

其中，θk均勻分布于[0，π)。

將兩節點之間的相對距離ρ定義為分離距離，ρ隨著節點運動不斷發生變化。這里約定初始時刻分離距離用ρ0表示，第k步分離距離用ρk來表示。將節點的通信半徑R用ε等分為L=Rε，如圖2所示，當鏈路存在時，分離距離ρ一定處在[0，Lε]區間內。如果ρ∈[(i-1)ε，iε]，i∈[1，L]，則定義ρ處于狀態si。鏈路斷開時，即ρN>R時的情況記為狀態sL+1。

隨著節點不斷運動，ρ所處的狀態將不斷變化，可以用具有吸收邊界的馬爾可夫鏈描述ρ的狀態變化過程，用P來表示狀態之間的一步轉移矩陣[12]。當ρ處于狀態sL+1時，表示節點2移出了節點1的通信范圍，鏈路斷開，sL+1為該馬爾可夫過程的吸收邊界。ρk-1∈si經過一步(即一個時隙)后到達ρk∈sj的概率為一步轉移概率Pij=Pr{ρk∈sj|ρk-1∈si}，分離距離ρ最多跨躍λ=「2(va+σv)ε個狀態。

用π(0)表示ρ0所處狀態的概率分布:

π(0)=(πs1(0)，πs2(0)，…，πsL(0)，πsL+1(0))(4)

用π(1)表示經過一步后ρ1所處狀態的概率分布

π(1)=(πs1(1)，πs2(1)，…，πsL(1)，πsL+1(1))=π(0)P(5)

同理可用π(k)表示經過k步后ρk所處狀態的概率分布

π(k)=(πs1(k)，πs2(k)，…，πsL(k)，πsL+1(k))=π(0)Pk (6)

一步轉移概率矩陣P可以寫成P=[P1，P2，…，Pi，…，PL+1]，Pi表示P中第i列向量。根據向量的乘法，可將式(5)(6)改寫為

π(1)=π(0)P=[π(0)P1，π(0)P2，…，π(0)Pi，…，π(0)PL+1](7)

π(k)=π(0)Pk=[π(0)Pk1，π(0)Pk2，…，π(0)Pki，…，π(0)PkL+1](8)

sL+1為吸收邊界，π(0)PL+1表示節點2經過一步移出節點1通信范圍的概率，即鏈路斷開概率。由馬爾可夫鏈的多步轉移性質，根據π(0)和P便可得ρ經多步轉移后所處狀態的概率，求出鏈路斷開概率。由式(8)可得以下重要公式

πsL+1(k)=π(0)PkL+1 (9)

表示初始狀態為π(0)分布的分離距離ρ0經過k步后鏈路斷開概率為π(0)PkL+1。

2.2 初始狀態分布π(0)

對于兩個節點分離距離ρ0確知，即ρ0初始狀態為si的情況下，初始狀態分布π(0)可以寫為

π(0)=(0，0，…，1，…，0) (10)

即π(0)向量中第i個元素為1。

2.3 一步轉移概率矩陣P的計算

由文獻[12]可知轉移概率矩陣P的Pij可表示為:

當L遠遠大于ε時，即當L足夠大，ε足夠小的時候，可以用如下近似表示ρk-1≈(i-12)ε，ρk≈(j-12)ε，因此，Pij可近似為

Pij≈ε#8226;fρk|ρk-1((j-12)ε|(i-12)ε)(11)

fρk|ρk-1(ρk|ρk-1)=∫2vmax02ρkf(vk)π4ρ2k-1v2k-(ρ2k-1+v2k-ρ2k)2dvk

(12)

fvk(vk)=∫vmaxvmin∫vmaxvminfvk，v1k，v2k(vk，v1k，v2k)dv1kdv2k=

∫vmaxvmin∫vmaxvminvkfv1k(v1k)fv2k(v2k)π4v21kv22k-(v21k+v22k-v2k)2dv1kdv2k(13)

為了求出上式，必須首先求出fv1k(v1k)和fv2k(v2k)，即單個節點運動速率的概率密度，由文獻[11]推導獲得

fv1k(v1k)=1αmax-αmin+1 ∑αmaxl=αmin ∑lj=11jfva(v1klj)E{T}+E{Tp}+

(M+1)βmax-βmin+1 ∑βmaxl=βmin ∑lj=1fvβ(j)(v1k)E{T}+E{Tp}+

Mεmax-εmin+1 ∑εmaxl=εmin ∑lj=1fvε(j)(v1k)E{T}+E{Tp}+

1γmax-γmin+1 ∑γmaxl=γmin ∑lj=1ll-j fvβ(v1kll-j)E{T}+E{Tp}+

E{Tp}δ(v1k)E{T}+E{Tp}

(14)

同理可得fv2k(v2k)。

在給定運動場景，節點通信范圍和節點運動參數確定的情況下，減緩通信暫盲現象，提高數據分組傳輸可靠性的關鍵在于如何設定節點之間的信標交換周期。針對網絡系統對可靠性的要求，可以設定一個鏈路斷開概率門限值PTh，

πsL+1(k)=π(0)PkL+1=PTh(15)

通過式(15)便可求出相應的信標周期T=k#8226;Δt。選定的PTh越小，得到的信標交換周期T越小，當PTh=0時，對應的信標交換周期T的最大值為R-ρ2vmax。其中ρ為兩個節點之間的初始分離距離，vmax為節點的最大運動速率。此時在下一個周期內，鏈路斷開概率πsL+1(k)=0，即不會產生通信暫盲現象。針對不同的鏈路，需要根據節點之間的分離距離ρ動態地計算信標交換周期。

3 算法模擬仿真

本文把采用鄰居節點表自適應構建與維護算法的貪婪地理路由協議稱為GVAR協議，并與GPSR協議在采用相同運動場景和業務場景條件下進行比較，兩者使用相同的空洞處理算法，只是構建鄰居節點表時GPSR協議采用周期性信標交換算法，而GVAR協議采用自適應信標交換算法。評價參數采用即時吞吐量、分組傳送成功率和控制開銷。仿真平臺使用NS-2.30[13]，仿真場景設置如表1所示。

表1 仿真場景設置

參數GPSRGVAR

場景大小150200250300350

150200250300350

節點數目1020304050

運動速率0，[0，2]，[1，3]，[2，4]，[3，5]，[4，6] m/s

通信半徑100 m

數據類型CBR 512 bit

數據速率10個/s

信標周期5s自適應動態計算

仿真時間100 s

圖3說明采用周期性信標交換的GPSR協議在相同的節點運動模型(vα∈[1，3]m/s)、相同的節點通信范圍(R=100 m)條件下，數據分組傳送成功率隨著網絡規模(通信鏈路的跳數)的增大而降低。而控制開銷也相應地增加， GVAR協議在控制開銷方面要優于GPSR協議，如圖4所示。

圖5說明在網絡規模相同、節點通信范圍相同的條件下，GPSR協議數據分組傳送成功率隨著節點運動劇烈程度的增加而降低，而GVAR協議的數據分組傳送成功率受網絡節點的運動劇烈程度影響不大，對網絡拓撲的動態變化具有很好的適應性，能適用于移動無線傳感器網絡。

圖6說明使用自適應信標交換算法的GVAR協議中控制開銷要低于使用周期性信標交換算法的GPSR協議。在GPSR協議中由于節點的運動速率的增大，數據分組成功傳送的總數減少，而信標分組數目基本不變，導致控制開銷有所增加。而在GVAR協議中，信標交換周期隨節點之間相對運動速率的增大而自適應地減小，產生的信標分組有所增加，導致控制開銷也有所增加。

4 結束語

本文針對Ad hoc網絡貪婪地理路由協議在移動環境中存在的通信暫盲現象進行了研究，在SGM移動模型的基礎上，分析節點移動對網絡連通性的影響，并提出了一種基于鏈路斷開概率的鄰居節點表自適應構建與維護算法。仿真結果表明，該算法能夠有效地消除通信暫盲現象，大大提高了數據傳輸可靠性，同時還降低了控制開銷，延長了網絡使用壽命。

參考文獻:

[1]KARP B， KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[C]//Proc of MOBICOM. 2000:243-254.

[2]KUHN F， WATTENHOFER R， ZHONG Y， et al. Geometric Ad hoc routing: of theory and practice[C]//Proc of the 23rd ACM Symposium on Principles of Distributed Computing (PODC’03).2003.

[3]KRANAKIS E， SINGH H， URRUTIA J. Compass routing on geometric networks[C]//Proc of the 11th Canadian Conference on Computation Geometry.1999.

[4]STOJMENOVIC I， LIN X. Loopfree hybrid singlepath/flooding routing algorithms with guaranteed delivery for wireless networks[J]. IEEE Trans on Parallel and Distributed Systems， 2001，12(10):1023-1032.

[5]張衡陽，李瑩瑩，劉云輝. 移動無線傳感器網絡自適應信標交換算法[J]. 軟件學報， 2008， 19(11): 3033-3041.

[6]WOLFSON O，JIANG L， SISTLA P， et al. Databases for tracking mobile units in real time[C]//Proc of the 7th International Conference on Database Theory.[S.l.]: Springer Verlag，1999:169-186.

[7]CHEN Q， SALIL S S， HASSAN M， et al. Adaptive position update in geographic routing[C]//Proc of IEEE International Conference on Communications.2006.

[8]HEISSENBUTTEL M， BRAUN T. Optimizing neighbor table accuracy of positionbased routing algorithms[C]//Proc of IEEE INFOCOM.2005.

[9]GIRUKA V C， SINGHAL M. Hello protocols for Ad hoc networks: overhead and accuracy tradeoffs[C]//Proc of the 6th IEEE International Symposium on World of Wireless Mobile and Multimedia Networks. 2005:354-361.

[10]SHEN Yao， CAI Yunze， XU Xiaoming. An adaptive scheme for neighbor discovery in mobile Ad hoc networks[J]. Journal of Shanghai Jiaotong University，2007，E-12(5).

[11]張衡陽，許丹，劉云輝，等.一種平滑的高斯—半馬爾可夫無線傳感器網絡移動模型[J]. 軟件學報，2008，19(7):1701-1715.

[12]SUNGSOON C， HAYES J P. Impact of mobility on connection in Ad hoc networks[C]//Proc of Wireless Communications and Networking Conference.2005:1650-1656.

[13]http://www.isi.edu/nsnam/ns/docstable/ns_doc.pdf[EB/OL].