江 濤,賀道德

（貴州工程技術應用學院信息工程學院，貴州　畢節(jié)　551700）

無線移動Ad-hocd-hoc網的一種新的地理路由方法

江 濤,賀道德

（貴州工程技術應用學院信息工程學院，貴州畢節(jié)551700）

分析無線Ad-hoc網現有的幾種主要路由算法類型,它們包括proactive類、reactive類。著重分析地理路由算法。對于近年來的研究熱點地理路由算法的類型進行分析，其中包括以路徑為優(yōu)化目標、以服務質量為優(yōu)化目標和以最小能量為優(yōu)化目標等幾種類型。在此基礎上，提出了概率路由算法的概念和一個新的算法。理論分析表明，該算法在該領域內是較好的算法。

無線Ad-hoc網；地理位置進行路由；概率路由算法

1　引言

無線Ad-hoc網是網絡的一個類別，它指的是這樣一類網絡：節(jié)點可移動，且每個節(jié)點都允許根據自己的愿望隨時加入或離開網絡，部分或所有節(jié)點可能隨時關機。因此，節(jié)點的位置和與網的連接狀態(tài)都是隨機的。

每個節(jié)點都具有路由能力，所有節(jié)點都既可以擔任路由器，又是終端用戶。網路沒有預先假設的路由中心，沒有擔任專門角色的設備(如專用路由器、交換機等)。

無線移動網實際上還分幾個子類：第一類是純粹Ad-hoc網(或稱移動的Ad-hoc網)，這種類型的Ad-hoc網所有節(jié)點都是移動的，簡稱為MANETs；第二類是WMNs，這種類型的網絡由Ad-hoc網+固定網組成；第三類是WSNs，這種類型的Ad-hoc網由帶傳感器的移動設備+車載Ad-hoc網組成。

本文研究第一種Ad-hoc網的情形，即全移動的Ad-hoc網。

全移動的Ad-hoc網(以下簡稱Ad-hoc網)更具動態(tài)性，網的形成常常是為完成一個特定任務，任務完成以后便解體，網的連接可能僅僅持續(xù)一個較短的時間段。

由于節(jié)點是全移動的，且每個節(jié)點都允許根據自己的愿望隨時加入或離開網絡，部分或所有節(jié)點可能隨時關機。因此，節(jié)點的位置和與網的連接狀態(tài)都是隨機的。這種網絡常出現在戰(zhàn)爭、地震等緊急情形。另外，無線移動Ad-hoc網還面臨干擾、路徑丟失、信號衰減等問題。由于受到節(jié)點本身發(fā)射功率的限制，節(jié)點轉發(fā)包只能局限于它附近的節(jié)點。因此，一個包從源節(jié)點傳遞到目標節(jié)點需要經過多個節(jié)點傳遞。這種情形簡稱為多跳(Multihop)。

根據無線移動網的特征，人們提出了兩類路由協議。一類稱為預先準備(proactive)的協議，一類稱為臨時處理(reactive)的協議。預先準備的協議通過在網中節(jié)點間發(fā)送一系列規(guī)則的更新信息來實現網絡拓撲結構的識別和儲存，而臨時處理類的協議不在網上發(fā)送更新信息來了解網絡的拓撲，當某個節(jié)點需要發(fā)送信息給某個目標節(jié)點時，發(fā)一個路由信息詢問其他節(jié)點。這兩類協議都有大量的算法。文獻[1]、[2]評價了預先準備(proactive)的協議、臨時處理(reactive)的協議和體系結構的協議三種基本協議類型，指出臨時處理類型的協議較好。

以上方法都因為要了解網絡的拓撲結構而需要發(fā)送詢問信息，使得網上存在許多冗余信息，而且還是依賴拓撲結構，通信和儲存方面的成本較高。

近年來，根據無線Ad-hoc網要求高效率、低成本的特性，人們提出了依據節(jié)點地理位置進行路由的新方法。這種路由方法是無線網領域內的一個新興研究熱點。這種稱為地理位置路由的方法中，包由源節(jié)點到目標節(jié)點的路由不依賴網絡標識或邏輯地址，而是依賴目標的地理位置[3]。這種路由方式不需要端到端的拓撲連接信息，不用構造并走一條簡單的靜態(tài)鏈路，也不用擔心拓撲路徑或鏈接中斷等問題。因為傳統意義上的路徑已經不存在了，同一對節(jié)點在不同時間傳遞包可能經歷的是不同的路徑。由于不用預存路由表，這種路由方式節(jié)省了開銷。一個節(jié)點只需存儲它附近的節(jié)點(鄰居)的位置信息。

當一個節(jié)點收到一個包時，它將查詢鄰居節(jié)點的位置信息表，根據某個地理位置選擇原則，選擇一個最適合的鄰居節(jié)點來實現下一跳。

但是，進一步的研究表明，為了更有效地路由，一個節(jié)點還是需要除鄰居之外的其他節(jié)點的位置信息。通常地理路由協議都使用某種位置服務來獲得節(jié)點的地理位置。這種地理位置服務很多，如[4]提出的格點定位服務。這種服務方法由指定為位置服務器的節(jié)點組成，它們的任務是負責接收和存儲某些節(jié)點的位置信息。當源節(jié)點需要知道目標節(jié)點的位置時，它將詢問這些位置服務器。

有了這些位置信息，地理路由協議仍然可以使用傳統的向前策略等方法來路由，所不同的是，路徑是依據節(jié)點的地理分布而不是拓撲結構來形成的。

2　地理路由協議的研究現狀

目前為止，人們對地理路由方法也進行大量的研究。地理路由方法有很多，例如貪心向前法和面路由法，這兩類方法是以源節(jié)點到目標節(jié)點的路徑為優(yōu)化目標的。也有許多以其他參數為優(yōu)化目標的，例如以服務質量為目標的地理路由協議，節(jié)省能量的路由協議，三維空間的地理路由協議，考慮安全性的地理路由協議，以及各種方法的改進方法。[5]

貪心向前法的基本思想是在每一跳中，把包傳給離目標節(jié)點最近的鄰居。這種方法簡單易行，效率好。最壞情況下的時間復雜度為O(d2)，d為源節(jié)點到目標節(jié)點的距離。貪心向前法的缺點是當一個節(jié)點不能找到一個比它自己離目標節(jié)點更近的節(jié)點時，它必須丟包。針對這個缺陷，產生了許多改進的方法。

面路由法是以平面圖為模型建立的一種方法。算法始終跟蹤與源節(jié)點到目標節(jié)點的連線相交的面，通過這些面上的節(jié)點傳遞信息，直到最終將信息傳遞到目標節(jié)點。它的復雜度為O(n)，n為網絡的節(jié)點數。

除了以上兩類方法，還有其他的地理路由方法。例如地理輔助路由法（LAR），使用位置來決定一個“請求區(qū)”，目標節(jié)點被認為是在該區(qū)域，然后傳遞包到該區(qū)域。

盡管地理路由的方法擺脫了拓撲結構的隨機性問題，但它還存在節(jié)點位置的隨機性問題。沒有考慮節(jié)點位置的隨機性，僅從固定地理位置結構來尋找到的最短路徑很難保證是實際上的最短路徑，因為位置的分布是隨機的，如圖1所示。（圖中虛線表示預想的路徑，實線表示實際的路徑。）

圖1　節(jié)點的移動路徑隨時改變

這是到目前為止我們所看到的研究文獻共同的不足。為了尋找實際上的最短路徑，應該從概率的角度來尋找最短路徑。

3　考慮概率因素的地理路由算法

下面考慮的仍是地理路由算法，仍然以優(yōu)化路徑為目標。但這里加入了概率的因素，即尋求概率意義上的最短路徑。稱這樣的方法為概率地理路由方法。

3.1全移動的Ad-Hoc網絡的隨機圖模型

設G=(V，E，W)，V為節(jié)點集，E為邊集，這里我們考慮圖G為完全圖，即任意一對節(jié)點之間均有一條邊。W為邊權值，表示兩節(jié)點之間的距離。由于節(jié)點是移動的，任何時刻任意一對節(jié)點之間的距離值W是隨機變化的。這樣的圖上任意一對節(jié)點間的最短路徑也是隨時變化的。我們的目標是要找到任意一對節(jié)點之間概率上最大的最短路徑。

就我們看到的資料，從概率的模型上考慮最短路徑的路由算法還非常少，更沒有形成一個類別。文獻[6]從數學的角度研究了平面上隨機點集上的最短路徑的概率分布，指出其最短路徑是服從泊松分布的Markov鏈，并證明了概率上的最短路徑的性質。

3.2移動網的概率最短路徑及數學證明

文獻[6]從概率的角度出發(fā)，采用Delaunay圖作為模型，證明了節(jié)點的地理位置分布、分布圖上的路徑都是服從泊松分布的隨機過程，且是Markov過程，并證明了源到目標節(jié)點連線（以下簡稱連線）為概率上的最短路徑，即連線為最短路徑的概率最大，并且在連線附近形成的最短路徑長度不超過4/π‖s-t‖，這里‖s-t‖是源節(jié)點到目標節(jié)點的歐幾里德距離（這里省略了數學證明的過程）。

在此基礎上，他們提出了一個找到概率上最短路徑的鄰居節(jié)點選擇原則：在選擇下一跳時，選擇靠近連線最近的鄰居，如圖2所示。

圖2　選擇靠近源-目標節(jié)點最近的鄰居

3.3我們所做的工作

首先，如果我們這樣假設：考慮節(jié)點的移動距離Δx與通信距離S相比，要小得多的情形下，即：

則可以粗略地認為節(jié)點移動的距離Δx可以忽略，即認為節(jié)點是近似靜止的，不移動的。在這個假設下，顯然我們看到，兩節(jié)點間的最短路徑就是兩節(jié)點的連線。再考慮到節(jié)點的發(fā)射功率限制，下一跳自然應選擇鄰居中最靠近連線的節(jié)點。

以上的簡化模型實際上間接地論證了文獻[6]的結論的正確性。

其次，我們綜合面路由法、文獻[6]提出的概率方法、以及我們這里的簡化模型，發(fā)現在確定下一跳的節(jié)點時，選擇“兩節(jié)點連線附近節(jié)點”的選擇策略，是這幾種方法一致推薦的方法。這表明該方法是有效的，是好算法。

另外，我們引用文獻[6]的結論，看到這個方法獲得的最短路徑是概率較大的最短路徑。

3.4概率最短路徑路由算法

綜上所述，我們得到概率上最短路徑的路由算法如下：

(1)在功率允許的情況下，直接沿著兩節(jié)點的連線方向將包發(fā)到目標節(jié)點即可。

(2)在功率不允許的情況下，根據以下原則找多跳節(jié)點：

(a)沿著兩節(jié)點的連線方向，找靠近連線最近的節(jié)點；

(b)如果所選節(jié)點失效(不在線)，則找次靠近連線的節(jié)點，以此類推。

(3)傳遞信息到找到的節(jié)點。

(4)循環(huán)以上方法，直到將信息傳遞到目標節(jié)點。

注意到，由于節(jié)點A和鄰居節(jié)點B移動速度相對于電信號速率要慢得多，所以發(fā)包的時間Δt內，A、B的位置變化可以忽略不計，如圖3所示。

圖3　發(fā)包過程A、B有位移

這里提出的算法最大的特點是簡單，丟包的可能性小，真正實現了最短路徑傳送。這個算法的時間復雜度為O(m*n)，m為平均鄰居數，n為多跳次數。算法的效率高。

因此，對于全移動的Ad-Hoc網絡來說，我們認為這是一個較好的路由算法。

4　實驗結果及討論

我們以多跳數為優(yōu)化目標。實驗隨機產生50個節(jié)點的圖2個，125節(jié)點的圖2個，320節(jié)點的圖2個。隨機圖接近均勻分布。每個圖取2對節(jié)點，節(jié)點對取自網絡周邊上。表中的多跳數是2個圖上4對節(jié)點的平均多跳數。我們設置網絡覆蓋的地理范圍相同，節(jié)點數增加，從而節(jié)點密度增加，則適當調小節(jié)點的發(fā)射功率范圍。節(jié)點功率范圍分別約為網絡半徑的1/4，1/8，1/16。實驗結果如表一所示。

表一　實驗結果

實驗結果表明，本文提出的概率算法在靜態(tài)圖上性能略差于貪心向前算法，接近貪心向前算法。但是，如果將圖的動態(tài)性考慮進去，概率算法的確是好算法，貪心向前算法沒有考慮概率因素。

5　結論與進一步的工作

本文研究了無線Ad-hoc網的路由問題。分析比較了目前為止的各種算法。提出了一個簡單的路由算法。面路由法，文獻[6]提出的概率方法，和我們這里的簡化模型，都一致得到兩節(jié)點連線附近的選擇策略，表明該方法是有效的，是好算法。由于是概率上的最短路徑，因此也是概率上的最小能量路徑，也是最小多跳次數的路徑，因為這幾個參數是一致的[9][10]。

進一步的工作是研究概率算法的節(jié)能效能。另外，文獻[7]指出基于Delaunay剖分圖不適合于Ad Hoc網的建模。如果是這樣，是否可把隨機分布的點集模型（也就是Delaunay圖）改為用文獻[8]提出的隨機弧長模型，這些都是進一步可做的工作。

[1]Muamer N.Mohammed,Norrozila Sulaiman,“Performance Analysis of DSR,AODV On-Demand Routing Protocols in Mobile Ad Hoc Networks”[J].Advanced Science Letters,2014(l):359-363.

[2]Liliana Enciso Quispe etc.,“Behavior of Ad Hoc routing protocols,Analysed for emergency and resue scenarios,on a real urban area”[J].Expert Systems with Applications,2014(41):2565-2573.

[3]I.Stojmenovic and X.Lin,“Power-aware Localized routing in Wireless Networks”[J].IEEE Trans.Parellels Distrib.Syst.,2001(11):1122-1133.

[4]J.Li,J.Jannotti etc.，”A scalable Location service for geographica Ad hoc routing”InProc.6thannual int. conf.on Mobile Compt.&Networking,ser.MobiCom’oo[M].New York:NY,USA:ACM,2000: 120-130.

[5]F.Cadgar,Kevin Curran etc.,“A survey of geographical Routing in Wireless Ad-hoc Networks”[J]. IEEE communications and Tutorials,2013(2):Second Quarter.

[6]F.Baccelli.K.Tchoumatehenko and S.Zuyev,“Markov Pths on the Possion–Delaunary Graph with Application to Routing in Mobile Networks”[J].Adv.Appl.Prob.(SGSA).2000(32):1-18.

[7]Fabian Kuhn etc.,“An Algorithmic Approach to Geographic Routing In Ad Hoc and Sensor Networks”[J].IEEE/ACM TRANACTION ON NETWORKING,2008(1):FEBRUARY.

[8]Mohammed Hessan Olya,“Applying Dijkstra algorithm for general shortest path problem with normal Probability distribution arc length”[J].J.Operational Research,2014(21):2.

[9]Lina Yuan,“Research on energy-saving strategies for Wireless Sensor Networks”[C]//2013年貴州省計算機學會年會論文集，2013.

[10]Ivan Stojmenovic,Xue Lin,“Power–Aware Localized Routing in Wireless Networks”[J].IEEE Trans. On Parallel and Distributed Systems,2001(11):Nov.

A New Routing Algorithm for Wireless Mobile Ad-hoc Network

JIANG Tao,HE Dao-de
（School of Information Engineering of Guizhou University of Engineering Science,Bijie, Guizhou551700,China）

Analyzing several main types of routing algorithm of wireless Ad-hoc network,we get proac?tive and reactive types,with emphasis on geographical routing algorithm.Analyzing types of routing algo?rithm of geographical routing the current research hotspot of the recent years,it concludes types of optyimiza?tiom target basing on routing,service quality and minimum energy.In this paper we have analyzed various routing methods of wireless Ad-hoc network，and proposed a new idea on probabilistic routing，and present a new method that is a better method by now.

Ad-hoc Network;Geographical Routing;Probabilistic Routing

TP391.4

A

2096-0239（2016）02-0150-05

（責編：彭麟淋責校：明茂修）

2016-01-25

江濤(1963-),男,貴州納雍人,貴州工程技術應用學院信息工程學院副教授。研究方向：圖算法。

賀道德(1979-),男，湖南常德人,貴州工程技術應用學院信息工程學院講師。研究方向：網格與Web Service。