江 濤,賀道德

（貴州工程技術(shù)應(yīng)用學(xué)院信息工程學(xué)院，貴州　畢節(jié)　551700）

無(wú)線移動(dòng)Ad-hocd-hoc網(wǎng)的一種新的地理路由方法

江 濤,賀道德

（貴州工程技術(shù)應(yīng)用學(xué)院信息工程學(xué)院，貴州畢節(jié)551700）

分析無(wú)線Ad-hoc網(wǎng)現(xiàn)有的幾種主要路由算法類型,它們包括proactive類、reactive類。著重分析地理路由算法。對(duì)于近年來(lái)的研究熱點(diǎn)地理路由算法的類型進(jìn)行分析，其中包括以路徑為優(yōu)化目標(biāo)、以服務(wù)質(zhì)量為優(yōu)化目標(biāo)和以最小能量為優(yōu)化目標(biāo)等幾種類型。在此基礎(chǔ)上，提出了概率路由算法的概念和一個(gè)新的算法。理論分析表明，該算法在該領(lǐng)域內(nèi)是較好的算法。

無(wú)線Ad-hoc網(wǎng)；地理位置進(jìn)行路由；概率路由算法

1　引言

無(wú)線Ad-hoc網(wǎng)是網(wǎng)絡(luò)的一個(gè)類別，它指的是這樣一類網(wǎng)絡(luò)：節(jié)點(diǎn)可移動(dòng)，且每個(gè)節(jié)點(diǎn)都允許根據(jù)自己的愿望隨時(shí)加入或離開網(wǎng)絡(luò)，部分或所有節(jié)點(diǎn)可能隨時(shí)關(guān)機(jī)。因此，節(jié)點(diǎn)的位置和與網(wǎng)的連接狀態(tài)都是隨機(jī)的。

每個(gè)節(jié)點(diǎn)都具有路由能力，所有節(jié)點(diǎn)都既可以擔(dān)任路由器，又是終端用戶。網(wǎng)路沒(méi)有預(yù)先假設(shè)的路由中心，沒(méi)有擔(dān)任專門角色的設(shè)備(如專用路由器、交換機(jī)等)。

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

本文研究第一種Ad-hoc網(wǎng)的情形，即全移動(dòng)的Ad-hoc網(wǎng)。

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

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

根據(jù)無(wú)線移動(dòng)網(wǎng)的特征，人們提出了兩類路由協(xié)議。一類稱為預(yù)先準(zhǔn)備(proactive)的協(xié)議，一類稱為臨時(shí)處理(reactive)的協(xié)議。預(yù)先準(zhǔn)備的協(xié)議通過(guò)在網(wǎng)中節(jié)點(diǎn)間發(fā)送一系列規(guī)則的更新信息來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的識(shí)別和儲(chǔ)存，而臨時(shí)處理類的協(xié)議不在網(wǎng)上發(fā)送更新信息來(lái)了解網(wǎng)絡(luò)的拓?fù)?，?dāng)某個(gè)節(jié)點(diǎn)需要發(fā)送信息給某個(gè)目標(biāo)節(jié)點(diǎn)時(shí)，發(fā)一個(gè)路由信息詢問(wèn)其他節(jié)點(diǎn)。這兩類協(xié)議都有大量的算法。文獻(xiàn)[1]、[2]評(píng)價(jià)了預(yù)先準(zhǔn)備(proactive)的協(xié)議、臨時(shí)處理(reactive)的協(xié)議和體系結(jié)構(gòu)的協(xié)議三種基本協(xié)議類型，指出臨時(shí)處理類型的協(xié)議較好。

以上方法都因?yàn)橐私饩W(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)而需要發(fā)送詢問(wèn)信息，使得網(wǎng)上存在許多冗余信息，而且還是依賴拓?fù)浣Y(jié)構(gòu)，通信和儲(chǔ)存方面的成本較高。

近年來(lái)，根據(jù)無(wú)線Ad-hoc網(wǎng)要求高效率、低成本的特性，人們提出了依據(jù)節(jié)點(diǎn)地理位置進(jìn)行路由的新方法。這種路由方法是無(wú)線網(wǎng)領(lǐng)域內(nèi)的一個(gè)新興研究熱點(diǎn)。這種稱為地理位置路由的方法中，包由源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路由不依賴網(wǎng)絡(luò)標(biāo)識(shí)或邏輯地址，而是依賴目標(biāo)的地理位置[3]。這種路由方式不需要端到端的拓?fù)溥B接信息，不用構(gòu)造并走一條簡(jiǎn)單的靜態(tài)鏈路，也不用擔(dān)心拓?fù)渎窂交蜴溄又袛嗟葐?wèn)題。因?yàn)閭鹘y(tǒng)意義上的路徑已經(jīng)不存在了，同一對(duì)節(jié)點(diǎn)在不同時(shí)間傳遞包可能經(jīng)歷的是不同的路徑。由于不用預(yù)存路由表，這種路由方式節(jié)省了開銷。一個(gè)節(jié)點(diǎn)只需存儲(chǔ)它附近的節(jié)點(diǎn)(鄰居)的位置信息。

當(dāng)一個(gè)節(jié)點(diǎn)收到一個(gè)包時(shí)，它將查詢鄰居節(jié)點(diǎn)的位置信息表，根據(jù)某個(gè)地理位置選擇原則，選擇一個(gè)最適合的鄰居節(jié)點(diǎn)來(lái)實(shí)現(xiàn)下一跳。

但是，進(jìn)一步的研究表明，為了更有效地路由，一個(gè)節(jié)點(diǎn)還是需要除鄰居之外的其他節(jié)點(diǎn)的位置信息。通常地理路由協(xié)議都使用某種位置服務(wù)來(lái)獲得節(jié)點(diǎn)的地理位置。這種地理位置服務(wù)很多，如[4]提出的格點(diǎn)定位服務(wù)。這種服務(wù)方法由指定為位置服務(wù)器的節(jié)點(diǎn)組成，它們的任務(wù)是負(fù)責(zé)接收和存儲(chǔ)某些節(jié)點(diǎn)的位置信息。當(dāng)源節(jié)點(diǎn)需要知道目標(biāo)節(jié)點(diǎn)的位置時(shí)，它將詢問(wèn)這些位置服務(wù)器。

有了這些位置信息，地理路由協(xié)議仍然可以使用傳統(tǒng)的向前策略等方法來(lái)路由，所不同的是，路徑是依據(jù)節(jié)點(diǎn)的地理分布而不是拓?fù)浣Y(jié)構(gòu)來(lái)形成的。

2　地理路由協(xié)議的研究現(xiàn)狀

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

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

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

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

盡管地理路由的方法擺脫了拓?fù)浣Y(jié)構(gòu)的隨機(jī)性問(wèn)題，但它還存在節(jié)點(diǎn)位置的隨機(jī)性問(wèn)題。沒(méi)有考慮節(jié)點(diǎn)位置的隨機(jī)性，僅從固定地理位置結(jié)構(gòu)來(lái)尋找到的最短路徑很難保證是實(shí)際上的最短路徑，因?yàn)槲恢玫姆植际请S機(jī)的，如圖1所示。（圖中虛線表示預(yù)想的路徑，實(shí)線表示實(shí)際的路徑。）

圖1　節(jié)點(diǎn)的移動(dòng)路徑隨時(shí)改變

這是到目前為止我們所看到的研究文獻(xiàn)共同的不足。為了尋找實(shí)際上的最短路徑，應(yīng)該從概率的角度來(lái)尋找最短路徑。

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

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

3.1全移動(dòng)的Ad-Hoc網(wǎng)絡(luò)的隨機(jī)圖模型

設(shè)G=(V，E，W)，V為節(jié)點(diǎn)集，E為邊集，這里我們考慮圖G為完全圖，即任意一對(duì)節(jié)點(diǎn)之間均有一條邊。W為邊權(quán)值，表示兩節(jié)點(diǎn)之間的距離。由于節(jié)點(diǎn)是移動(dòng)的，任何時(shí)刻任意一對(duì)節(jié)點(diǎn)之間的距離值W是隨機(jī)變化的。這樣的圖上任意一對(duì)節(jié)點(diǎn)間的最短路徑也是隨時(shí)變化的。我們的目標(biāo)是要找到任意一對(duì)節(jié)點(diǎn)之間概率上最大的最短路徑。

就我們看到的資料，從概率的模型上考慮最短路徑的路由算法還非常少，更沒(méi)有形成一個(gè)類別。文獻(xiàn)[6]從數(shù)學(xué)的角度研究了平面上隨機(jī)點(diǎn)集上的最短路徑的概率分布，指出其最短路徑是服從泊松分布的Markov鏈，并證明了概率上的最短路徑的性質(zhì)。

3.2移動(dòng)網(wǎng)的概率最短路徑及數(shù)學(xué)證明

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

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

圖2　選擇靠近源-目標(biāo)節(jié)點(diǎn)最近的鄰居

3.3我們所做的工作

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

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

以上的簡(jiǎn)化模型實(shí)際上間接地論證了文獻(xiàn)[6]的結(jié)論的正確性。

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

另外，我們引用文獻(xiàn)[6]的結(jié)論，看到這個(gè)方法獲得的最短路徑是概率較大的最短路徑。

3.4概率最短路徑路由算法

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

(1)在功率允許的情況下，直接沿著兩節(jié)點(diǎn)的連線方向?qū)l(fā)到目標(biāo)節(jié)點(diǎn)即可。

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

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

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

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

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

注意到，由于節(jié)點(diǎn)A和鄰居節(jié)點(diǎn)B移動(dòng)速度相對(duì)于電信號(hào)速率要慢得多，所以發(fā)包的時(shí)間Δt內(nèi)，A、B的位置變化可以忽略不計(jì)，如圖3所示。

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

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

因此，對(duì)于全移動(dòng)的Ad-Hoc網(wǎng)絡(luò)來(lái)說(shuō)，我們認(rèn)為這是一個(gè)較好的路由算法。

4　實(shí)驗(yàn)結(jié)果及討論

我們以多跳數(shù)為優(yōu)化目標(biāo)。實(shí)驗(yàn)隨機(jī)產(chǎn)生50個(gè)節(jié)點(diǎn)的圖2個(gè)，125節(jié)點(diǎn)的圖2個(gè)，320節(jié)點(diǎn)的圖2個(gè)。隨機(jī)圖接近均勻分布。每個(gè)圖取2對(duì)節(jié)點(diǎn)，節(jié)點(diǎn)對(duì)取自網(wǎng)絡(luò)周邊上。表中的多跳數(shù)是2個(gè)圖上4對(duì)節(jié)點(diǎn)的平均多跳數(shù)。我們?cè)O(shè)置網(wǎng)絡(luò)覆蓋的地理范圍相同，節(jié)點(diǎn)數(shù)增加，從而節(jié)點(diǎn)密度增加，則適當(dāng)調(diào)小節(jié)點(diǎn)的發(fā)射功率范圍。節(jié)點(diǎn)功率范圍分別約為網(wǎng)絡(luò)半徑的1/4，1/8，1/16。實(shí)驗(yàn)結(jié)果如表一所示。

表一　實(shí)驗(yàn)結(jié)果

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

5　結(jié)論與進(jìn)一步的工作

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

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

[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年貴州省計(jì)算機(jī)學(xué)會(huì)年會(huì)論文集，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

（責(zé)編：彭麟淋責(zé)校：明茂修）

2016-01-25

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

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