基于位置信息的自組織網(wǎng)絡(luò)路由算法研究

范溥

摘要：隨著定位技術(shù)的發(fā)展，位置信息的獲取成本也在逐步降低，由于借助于位置信息可以使路由的開銷大大降低，因此人們也越來越重視自組織網(wǎng)絡(luò)基于位置信息的算法研究，為了使這種算法更成熟，性能更優(yōu)良，該文分析了現(xiàn)有基于位置信息的路由算法，并重點(diǎn)研究了單播路由算法中的貪婪轉(zhuǎn)發(fā)算法與空洞處理算法，以供同行參考。

關(guān)鍵詞：位置信息；自組織網(wǎng)絡(luò)；貪婪轉(zhuǎn)發(fā)算法；空洞處理算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）04-0037-02

無線自組織網(wǎng)絡(luò)屬于多跳網(wǎng)絡(luò)中的一種，它不同于之前的無線單跳通信網(wǎng)絡(luò)。對(duì)于無線單跳網(wǎng)絡(luò)來說需要固定網(wǎng)絡(luò)設(shè)施做支撐，如要實(shí)現(xiàn)數(shù)據(jù)的轉(zhuǎn)發(fā)需要由基站來支持，而對(duì)于無線自組織網(wǎng)絡(luò)來說進(jìn)行通信時(shí)不需設(shè)施作支持，并且無線自組織網(wǎng)絡(luò)的各節(jié)點(diǎn)不但可以當(dāng)做終端來收發(fā)數(shù)據(jù)，而且還可當(dāng)做一種路由器來轉(zhuǎn)發(fā)各種數(shù)據(jù)，由于新特征在無線自組織網(wǎng)絡(luò)的融入，這也造成了之前的路由算法不能適應(yīng)新形勢(shì)的發(fā)展，于是人們開始探索研究基于位置信息的自組織網(wǎng)絡(luò)路由算法。

1 基于位置信息的路由算法

由于自組織網(wǎng)絡(luò)不存在固定的基礎(chǔ)設(shè)施，自組織網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的通訊只能在通訊范圍內(nèi)，所以任意節(jié)點(diǎn)對(duì)之間要想實(shí)現(xiàn)自由通訊，只能依靠多個(gè)節(jié)點(diǎn)間的相互轉(zhuǎn)發(fā)來實(shí)現(xiàn)，這也就是我們通常所說的多跳路由。按照路由算法使用的信息情況這種算法大致分為兩類：基于位置信息的路由算法與基于拓?fù)湫畔⒌穆酚伤惴āＯ旅嫖覀兙椭攸c(diǎn)介紹一下基于位置信息的路由算法。

以節(jié)點(diǎn)的具體位置信息為基礎(chǔ)進(jìn)行轉(zhuǎn)發(fā)是基于位置信息的路由算法的主要工作方式，它不同于最初的只借助目的節(jié)點(diǎn)位置信息的轉(zhuǎn)發(fā)方式，當(dāng)前的基于位置信息的路由算法不僅要用到目的節(jié)點(diǎn)的位置信息，而且還要用到節(jié)點(diǎn)自身位置信息與一跳后的鄰居節(jié)點(diǎn)位置信息，在這個(gè)轉(zhuǎn)發(fā)的過程中，中間節(jié)點(diǎn)對(duì)下一跳的具體轉(zhuǎn)發(fā)節(jié)點(diǎn)可自主進(jìn)行選擇。所以該節(jié)點(diǎn)到相應(yīng)目的節(jié)點(diǎn)間的路徑不用具體的去進(jìn)行維護(hù)，也不用發(fā)送相關(guān)控制包來對(duì)路徑狀態(tài)進(jìn)行更新。由于網(wǎng)絡(luò)拓?fù)涞淖兓绊懝?jié)點(diǎn)下一跳的選擇也只是在該節(jié)點(diǎn)的一跳范圍之內(nèi)，因此網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，影響基于位置信息的路由算法要遠(yuǎn)小于基于拓?fù)湫畔⒌穆酚伤惴?，此外基于位置信息的路由算法局域性通常都比較好，因此它的網(wǎng)絡(luò)擴(kuò)展性也相對(duì)較好。

2 基于位置信息的單播路由算法

單播路由算法可實(shí)現(xiàn)從源節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)唯一連通路徑的構(gòu)建，若數(shù)據(jù)需要從源節(jié)點(diǎn)傳輸至目的節(jié)點(diǎn)時(shí)，可借助某種算法從相應(yīng)鄰居節(jié)點(diǎn)中挑選出某個(gè)節(jié)點(diǎn)來作為下一跳目標(biāo)，數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)的過程就是就是此算法在中間節(jié)點(diǎn)重復(fù)執(zhí)行的過程。就當(dāng)前的基于位置信息的路由算法而言，其中人們應(yīng)用比較多的一種算法就是貪婪轉(zhuǎn)發(fā)算法，它具有高效、簡單的特點(diǎn)，但這種算法有個(gè)局限性，用想利用它轉(zhuǎn)發(fā)數(shù)據(jù)，前提是當(dāng)前的網(wǎng)絡(luò)密度要足夠高，但實(shí)際部署的網(wǎng)絡(luò)，難免會(huì)有不連貫的區(qū)域出現(xiàn)在網(wǎng)絡(luò)局部，而貪婪算法遇到不連貫區(qū)域時(shí)，由于局部最小化問題會(huì)導(dǎo)致貪婪轉(zhuǎn)發(fā)算法的傳輸失敗，我們通常把造成貪婪轉(zhuǎn)發(fā)不能成功的不連貫區(qū)域統(tǒng)稱為通訊空洞，為了更好應(yīng)對(duì)貪婪轉(zhuǎn)發(fā)算法的這樣缺陷，人們研究了一種空洞處理算法，來承擔(dān)起遇到空洞時(shí)貪婪算法的轉(zhuǎn)發(fā)任務(wù)，實(shí)現(xiàn)路由任務(wù)的最終順利完成，所以貪婪轉(zhuǎn)發(fā)算法與空洞處理算法共同構(gòu)成了一個(gè)全面完善的路由協(xié)議。下面我們就分別介紹一下這兩種算法。

2.1貪婪轉(zhuǎn)發(fā)算法

根據(jù)某種標(biāo)準(zhǔn)以當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)位置信息以及目的節(jié)點(diǎn)位置信息為基礎(chǔ)，來進(jìn)行下一跳局部最優(yōu)節(jié)點(diǎn)的選擇，這種轉(zhuǎn)發(fā)方式并重復(fù)應(yīng)用于中間所有節(jié)點(diǎn)，直到目的節(jié)點(diǎn)的到達(dá)，這就是貪婪轉(zhuǎn)發(fā)算法。當(dāng)前，人們根據(jù)算法選擇下一跳節(jié)點(diǎn)標(biāo)準(zhǔn)的不同，已經(jīng)研究出了很多中貪婪轉(zhuǎn)發(fā)算法。

最初的貪婪轉(zhuǎn)發(fā)算法選擇最優(yōu)下一跳節(jié)點(diǎn)的標(biāo)準(zhǔn)是依據(jù)幾何計(jì)算結(jié)果進(jìn)行的，其具體選擇過程如下圖1所示：

當(dāng)前節(jié)點(diǎn)用圖中的S表示，目的節(jié)點(diǎn)用D表示，不同的選擇標(biāo)準(zhǔn)，也會(huì)得到不同的下一跳節(jié)點(diǎn)，下面我們就總結(jié)一下各種貪婪轉(zhuǎn)發(fā)的形式：

1） 隨機(jī)轉(zhuǎn)發(fā)

從當(dāng)前的鄰居所有鄰居節(jié)點(diǎn)中隨機(jī)任意選擇一個(gè)距離目的節(jié)點(diǎn)更近的節(jié)點(diǎn)當(dāng)做下一跳的目標(biāo)節(jié)點(diǎn)，依次類推這就是隨機(jī)轉(zhuǎn)發(fā)過程。如在圖1中，S節(jié)點(diǎn)的鄰居節(jié)點(diǎn)有A、R、B、C、F，在這幾個(gè)節(jié)點(diǎn)中，A、B、C、F節(jié)點(diǎn)與目的節(jié)點(diǎn)的距離都比S節(jié)點(diǎn)本身近，所以S節(jié)點(diǎn)的下一跳節(jié)點(diǎn)可從這四個(gè)節(jié)點(diǎn)中隨機(jī)選取一個(gè)，這就是隨機(jī)轉(zhuǎn)發(fā)。

2） 最近方向轉(zhuǎn)發(fā)

最近方向轉(zhuǎn)發(fā)主要是按照在當(dāng)前節(jié)點(diǎn)連接目的節(jié)點(diǎn)的方向上，選擇一個(gè)距離目標(biāo)節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)作為最優(yōu)下一跳節(jié)點(diǎn)。在圖1中，依照這種轉(zhuǎn)發(fā)方式，C節(jié)點(diǎn)將作為S節(jié)點(diǎn)的最優(yōu)下一跳節(jié)點(diǎn)進(jìn)行各項(xiàng)任務(wù)的轉(zhuǎn)發(fā)。

3） MFR轉(zhuǎn)發(fā)

在利用MFR轉(zhuǎn)發(fā)時(shí)，節(jié)點(diǎn)的前進(jìn)值根據(jù)當(dāng)前節(jié)點(diǎn)與目的節(jié)點(diǎn)連線上的正交投影來定的，當(dāng)前節(jié)點(diǎn)選擇的下一跳最優(yōu)節(jié)點(diǎn)是全部鄰居節(jié)點(diǎn)中正向前進(jìn)值最大的節(jié)點(diǎn)。在如圖1所示，節(jié)點(diǎn)S與D連線上具有最大值投影的是A節(jié)點(diǎn)，所以S節(jié)點(diǎn)的下一跳節(jié)點(diǎn)將選擇A節(jié)點(diǎn)。

4） NFP轉(zhuǎn)發(fā)

在利用NFP轉(zhuǎn)發(fā)時(shí)，下一跳最優(yōu)節(jié)點(diǎn)我們選擇的是與節(jié)點(diǎn)SD連線方向上，所有當(dāng)前節(jié)點(diǎn)鄰居中，正向前進(jìn)值最小的鄰居節(jié)點(diǎn)。如圖1所示，S節(jié)點(diǎn)的最小正向前進(jìn)值的鄰居節(jié)點(diǎn)為G節(jié)點(diǎn)，所以S節(jié)點(diǎn)的最優(yōu)下一跳節(jié)點(diǎn)將選擇為G節(jié)點(diǎn)。

5） MAR轉(zhuǎn)發(fā)

MAR轉(zhuǎn)發(fā)是選擇的下一跳節(jié)點(diǎn)是距離目的節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)，如圖1所示，目的節(jié)點(diǎn)D最近的節(jié)點(diǎn)為E，所以當(dāng)前S節(jié)點(diǎn)的下一跳節(jié)點(diǎn)將選擇節(jié)點(diǎn)E。

2.2 空洞處理算法

在貪婪轉(zhuǎn)發(fā)失效的情況下，接下來的數(shù)據(jù)包轉(zhuǎn)發(fā)任務(wù)將由空洞處理算法來繼續(xù)作業(yè)，直到運(yùn)行環(huán)境能夠繼續(xù)讓貪婪轉(zhuǎn)發(fā)運(yùn)行為止，然后再由貪婪轉(zhuǎn)發(fā)算法來完成任務(wù)，若貪婪轉(zhuǎn)發(fā)一直都未能運(yùn)行，哪就由空洞處理算法來完成任務(wù)，下圖2為貪婪轉(zhuǎn)發(fā)算法失效示意圖。

如圖2所示，由于在S節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)中，任何一個(gè)鄰居節(jié)點(diǎn)到目的節(jié)點(diǎn)D的距離都遠(yuǎn)于A節(jié)點(diǎn)，這樣就造成了S節(jié)點(diǎn)無法利用貪婪轉(zhuǎn)發(fā)方式來進(jìn)行下一跳節(jié)點(diǎn)的選擇，所以，如果只單單借助貪婪轉(zhuǎn)發(fā)數(shù)據(jù)包將不能從當(dāng)前節(jié)點(diǎn)S向目的節(jié)點(diǎn)D順利傳輸。下面我們就來介紹幾種常見的空洞處理法，來順利解決此類問題。

1） 基于拓?fù)涞目斩刺幚矸?/p>

這種算法對(duì)空洞問題的處理是借助拓?fù)湫畔⑦M(jìn)行的，泛洪是這種算法中主要用到的方法，利用全網(wǎng)泛洪拓?fù)溥B通的具體路徑在全網(wǎng)范圍內(nèi)找到，但其存在一個(gè)致命的缺點(diǎn)就是需要的開銷通常都較高。為了減小其開銷，我們通常不采用直接去查找到目的節(jié)點(diǎn)的路徑，往往都是通過查找可以恢復(fù)貪婪轉(zhuǎn)發(fā)節(jié)點(diǎn)的路徑，來實(shí)現(xiàn)數(shù)據(jù)到目的地的最終傳輸。

2） 基于平面圖的空洞處理算法

這種算法主要是根據(jù)平面圖的特性來對(duì)數(shù)據(jù)包進(jìn)行傳輸，這種算法在處理貪婪轉(zhuǎn)發(fā)失效時(shí)的開銷通常都比較低，這主要是由于網(wǎng)絡(luò)平面圖具有局部性的特點(diǎn)。我們所說的平面圖是指一種非自交圖，它能夠在平面內(nèi)嵌入，RNG以及GG是當(dāng)前用來平面化處理網(wǎng)絡(luò)的主要方式。對(duì)網(wǎng)絡(luò)進(jìn)行平衡化處理過后，然后按照轉(zhuǎn)發(fā)策略自空洞邊緣開始轉(zhuǎn)發(fā)。

3） 基于幾何特性的空洞處理算法

通過網(wǎng)絡(luò)拓?fù)涞膸缀翁匦詠韺?duì)數(shù)據(jù)包進(jìn)行發(fā)送是該算法的主要工作模式，BOUDNHOLE算法是這類算法的代表，對(duì)于某節(jié)點(diǎn)貪婪轉(zhuǎn)發(fā)成功與否的判斷借助TENT規(guī)則來進(jìn)行，若判斷出該節(jié)點(diǎn)沒有成功，那么就用Stuck節(jié)點(diǎn)來表示該節(jié)點(diǎn)，并且還要繼續(xù)把這個(gè)空洞的所有Stuck節(jié)點(diǎn)全部找出來，在得到了同一空洞的所有Stuck節(jié)點(diǎn)之后，沿著Stuck節(jié)點(diǎn)進(jìn)行數(shù)據(jù)包的發(fā)送，直到貪婪轉(zhuǎn)發(fā)能正常進(jìn)行。

3 結(jié)束語

總之，隨著現(xiàn)代定位技術(shù)的飛速發(fā)展，基于位置信息的路由算法以其簡單、高效的優(yōu)勢(shì)，在自組織網(wǎng)絡(luò)路由算法的研究中也越來越受到人們的重視，我們可以推斷在不久的將來，在自組織網(wǎng)絡(luò)路由算法中基于位置信息的路由算法必然會(huì)成為主流，但就目前的基于位置信息的自組織網(wǎng)絡(luò)路由算法而言，性能還不是很好，還有很大的可提升空間，為此我們必須堅(jiān)持不懈，繼續(xù)進(jìn)行深入研究，只有這樣才能使這種算法的性能更優(yōu)良，才能使這種算法更好地為我們服務(wù)。

參考文獻(xiàn)：

[1] 胡淼，李劍峰.車載自組織網(wǎng)絡(luò)中基于貪婪算法的地理位置路由[J].中興通訊技術(shù)，2011（3）.

[2] 張永暉，林漳希，劉建華，等.基于位置信息的倉儲(chǔ)容遲網(wǎng)絡(luò)路由算法[J].電信科學(xué)，2012（11）.

[3] 侯守峰，周小佳，閆斌.無線傳感器網(wǎng)絡(luò)中基于位置信息的路由算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010（22）.