摘 要：介紹了Ad Hoc網(wǎng)絡(luò)的基本概念及其特點，分析了一種現(xiàn)有的基于AODV的混合網(wǎng)絡(luò)路由算法，并在這種算法的基礎(chǔ)上，提出了一種改進此算法的方案，使之減少網(wǎng)絡(luò)中占用帶寬的控制包數(shù)量，節(jié)約了有限的帶寬資源。最后，用NS網(wǎng)絡(luò)仿真工具對其進行了仿真分析，結(jié)果表明改進后的路由協(xié)議在減少控制包的數(shù)量和時延方面均有較好的表現(xiàn)。

關(guān)鍵詞：Ad Hoc；蜂窩網(wǎng)；AODV；GPS

中圖分類號：TN915 文獻標(biāo)識碼：B

文章編號：1004373X(2008)0305704

A Routing Algorithm in Integration of Cellular and Ad Hoc Network Based on Nodes Position

YANG Jinning，DUAN Jihai

(Guilin University of Electronic Technology，Guilin，541004，China)

Abstract：Basic concept of Ad Hoc network and routing algorithm of hybrid network are introduced and analysed.A routing algorithm in integration of cellular and Ad Hoc network based on nodes position to reduce the number of control packets is present.In order to show the efficiency of our protocol，NS has been used for all simulations，and the results show it is useful to study routing algorithms in integration of cellular and Ad Hoc network.

Keywords：Ad Hoc;cellular;AODV;GPS

1 引 言

“Ad Hoc”一詞來源于拉丁語，意思是“專用的、特定的為某一即將發(fā)生的特點目標(biāo)、事件或局勢而不為其他的”，通常也把Ad Hoc網(wǎng)絡(luò)稱為“自組織網(wǎng)絡(luò)”或“無線多跳網(wǎng)絡(luò)”[1]。Ad Hoc網(wǎng)絡(luò)作為一種新的組網(wǎng)方式，和常見的有線固定網(wǎng)絡(luò)、蜂窩無線網(wǎng)絡(luò)以及無線局域網(wǎng)相比具有以下特點：Ad Hoc網(wǎng)絡(luò)是一個自組織、自啟動的無線移動網(wǎng)絡(luò)，他不需要中心基站的支持，沒有固定的網(wǎng)絡(luò)架構(gòu)，具有多跳路由和移動終端的便攜性等。

近十年，隨著無線數(shù)據(jù)業(yè)務(wù)量的急劇增加，十分有限的數(shù)據(jù)信道資源已經(jīng)成為蜂窩網(wǎng)系統(tǒng)一個急待解決的問題。傳統(tǒng)蜂窩網(wǎng)中的通信都要通過基站或接入點實現(xiàn)，但由于頻率資源的有限，就算建立更多的基站，擁塞問題仍然存在。為了解決蜂窩網(wǎng)絡(luò)中的這些問題，我們將Ad Hoc網(wǎng)絡(luò)引入蜂窩網(wǎng)。Ad Hoc網(wǎng)絡(luò)在吞吐量，延時和節(jié)省功率等方面都有較好的性能，其缺點是不適合應(yīng)用到廣域網(wǎng)。綜合考慮兩種網(wǎng)絡(luò)的優(yōu)點和劣勢，可以將Ad Hoc網(wǎng)絡(luò)與蜂窩網(wǎng)結(jié)合，彌補對方的缺陷，提高網(wǎng)絡(luò)的性能。通過Ad Hoc網(wǎng)絡(luò)可以實現(xiàn)蜂窩系統(tǒng)的無縫隙覆蓋，消除盲點，提供高的數(shù)據(jù)業(yè)務(wù)；而通過蜂窩網(wǎng)則可簡化Ad Hoc網(wǎng)絡(luò)的路由機制，提供安全性能和服務(wù)質(zhì)量。

為了實現(xiàn)兩種網(wǎng)絡(luò)的有機結(jié)合，須改進以前單一網(wǎng)絡(luò)的路由算法，以適應(yīng)新的混合網(wǎng)絡(luò)。

2 混合網(wǎng)絡(luò)的路由算法AODV_I

Ad Hoc雖然有多種路由協(xié)議，但可實現(xiàn)Ad Hoc網(wǎng)絡(luò)與蜂窩互連的只有DSDV，并且，DSDV在移動場景下的性能非常差。Ad Hoc網(wǎng)絡(luò)中比較經(jīng)典的一些路由協(xié)議如AODV[2]協(xié)議，并不支持Ad Hoc節(jié)點接入基站的路由搜索，只有對AODV協(xié)議進行改進，使他的路由協(xié)議的發(fā)現(xiàn)消息不僅能夠發(fā)現(xiàn)移動節(jié)點還可以發(fā)現(xiàn)基站，才能支持移動節(jié)點到固定基站以及有線網(wǎng)絡(luò)的尋路。

文獻[3—5]在MCN[6]混合體系結(jié)構(gòu)的基礎(chǔ)上提出了AODV協(xié)議的改進思想，其主要思想是擴展AODV協(xié)議的發(fā)現(xiàn)消息，使其不僅能夠發(fā)現(xiàn)移動節(jié)點，還可以發(fā)現(xiàn)基站；而改進方案中要求發(fā)現(xiàn)基站的原因是在MCN體系中，基站也被當(dāng)成了節(jié)點，只不過他與他覆蓋范圍內(nèi)的節(jié)點實行的是單跳連接，覆蓋范圍以外的節(jié)點實行的是多跳連接，而混合網(wǎng)絡(luò)則被看成是一個覆蓋范圍更大的具有分層結(jié)構(gòu)的Ad Hoc網(wǎng)絡(luò)。為了方便起見，在這里把經(jīng)過發(fā)現(xiàn)消息和請求消息擴展后的AODV協(xié)議稱為AODV_I。路由請求消息在原路由請求消息中加入全局地址解析標(biāo)志，記為I-FLAG。這個標(biāo)志意味著源節(jié)點發(fā)起的是一次全局連接，而不僅是移動節(jié)點之間。

擴展后的路由請求消息記為RREQ_I，結(jié)構(gòu)如圖1所示。

圖1 擴展后的RREQ消息格式

其中：RREQs消息的類型設(shè)置為1；J(Jion Flag)是為組播預(yù)留的加入標(biāo)識；R(Repair Flag)是為組播預(yù)留的修復(fù)標(biāo)識；G(Gratuitous RREP Flag)用于指示一個RREPs(Route Reply)是否向目的IP地址字段指明的節(jié)點進行單播；D(Destination only flag)表示只有目的能回應(yīng)RREQ；U(Unknown sequence number)表示目的序列號是未知的。

擴展后的路由應(yīng)答消息也在原有的路由應(yīng)答消息上加入了全局地址解析標(biāo)記(I_FLAG)。擴展后的路由應(yīng)答消息記為RREP_I，其結(jié)構(gòu)見圖2。

圖2 擴展后的RREP消息格式

擴展后的RREP消息的類型設(shè)置為2；R(Repair flag)用于組播；A(Acknowledgment required)用于確認。

3 AODV_I路由算法的改進

AODV_I僅僅是在基站處實現(xiàn)了現(xiàn)有的AODV算法，使得AODV算法并不僅限于某個小區(qū)域內(nèi)，并可以通過基站的有線連接使得間隔較遠的節(jié)點可以正常通信。但這樣的算法對于原有AODV來說，只相當(dāng)于將原有的適合平面模型的Ad Hoc路由協(xié)議擴展到了分級結(jié)構(gòu)中去，并沒有解決AODV_I自身所帶有的一些缺陷。因此，提出了基于節(jié)點位置的AODV_I的改進方案，使得改進后的AODV_I路由算法在控制包的數(shù)量上有所減少，以致更能適應(yīng)Ad Hoc和蜂窩混合網(wǎng)絡(luò)的路由算法。

3.1 基于節(jié)點位置的路由轉(zhuǎn)發(fā)思想

目前GPS技術(shù)已經(jīng)比較成熟了，小巧、輕便以及低成本的特點使得他們能很容易地成為移動節(jié)點的一部分，為與之相連的移動節(jié)點提供當(dāng)前的地理位置信息。利用這些位置信息，可以使混合網(wǎng)絡(luò)的性能得到改善。例如：在自組網(wǎng)中利用位置信息，可以使節(jié)點在尋找路由時避免簡單的泛洪；利用相鄰節(jié)點或目的節(jié)點或目的節(jié)點的位置信息，可以提高路由尋找的效率。

在這種形勢下，提出一種通過使用GPS(Global Positioning System)發(fā)現(xiàn)節(jié)點位置的路由算法來改進AODV_I。在這種算法中，節(jié)點通過GPS獲取自己地理位置信息，并通過節(jié)點間交互位置信息，使得每個節(jié)點都能知道網(wǎng)絡(luò)中其他節(jié)點的坐標(biāo)，源節(jié)點只需朝著目的節(jié)點的方向發(fā)送控制包。這種算法與AODV_I所使用的擴張環(huán)搜索技術(shù)相比減少了控制包的數(shù)量，節(jié)約了網(wǎng)絡(luò)資源。

文中將該“目的節(jié)點的方向”稱為“轉(zhuǎn)發(fā)區(qū)域”，即節(jié)點只向其轉(zhuǎn)發(fā)區(qū)域中的一跳鄰節(jié)點發(fā)送分組。為了限制轉(zhuǎn)發(fā)區(qū)域，源節(jié)點還要知道目的節(jié)點的位置信息。在這種轉(zhuǎn)發(fā)思想里，網(wǎng)絡(luò)中的每一個節(jié)點須周期性的向最近的基站登記自身的位置信息(節(jié)點的坐標(biāo))，在基站覆蓋范圍內(nèi)的節(jié)點直接登記，范圍外的節(jié)點通過多跳依靠其他節(jié)點協(xié)助登記?；揪S護一個位置表項來管理與之進行登記過的節(jié)點的位置和相關(guān)信息。

當(dāng)一個源節(jié)點S要求得到一個目的節(jié)點D的位置信息時，他就給最近一個時間與他登記過的基站發(fā)送一個請求，基站收到請求后，將從其位置表項中尋找有關(guān)目的節(jié)點的位置信息。如果存在相關(guān)記錄，基站就會把目的節(jié)點的位置信息提供給源節(jié)點；如果不存在此相關(guān)記錄，收到源節(jié)點請求的基站就會把請求發(fā)給附近的其他基站，來尋找目的節(jié)點的相關(guān)記錄。當(dāng)目的位置信息在一個特定的時間間隔內(nèi)都沒有能夠被源節(jié)點收到，將認為目的節(jié)點無法定位，只能使用原AODV_I的路由發(fā)現(xiàn)策略，在這種情況下，控制包的數(shù)量沒有辦法得到減少。

3.2 轉(zhuǎn)發(fā)區(qū)域的確定

為了計算方便，把轉(zhuǎn)發(fā)區(qū)域限制在一個角度等于2α，半徑等于R，其中一條邊與X軸重合的扇形BSA里。如圖3所示，點S是坐標(biāo)軸的原點，用S和D對應(yīng)源節(jié)點和目的節(jié)點的位置，即只有在這個扇形區(qū)域里的節(jié)點才能轉(zhuǎn)發(fā)目的節(jié)點D的控制包。圖中的扇形B′SA′的頂角和扇形BSA的頂角呈對頂角關(guān)系，且半徑相等，他是在數(shù)學(xué)推理的過程中得到的另一個方向與BSA相反的區(qū)域。

圖3 轉(zhuǎn)發(fā)區(qū)域數(shù)學(xué)模型

很有必要知道一個節(jié)點是否能夠轉(zhuǎn)發(fā)控制包。首先，要介紹當(dāng)XS≠XD且2α<90°時的搜索區(qū)域的性質(zhì)。限制α的值是因為控制包只能朝著目的節(jié)點的方向轉(zhuǎn)發(fā)。

首先決定D的取值。用Y=tan α#8226;X且XS≠XD表示穿過S和D的直線(Xi表示節(jié)點i的

X軸的坐標(biāo))。

性質(zhì)1可以用來決定弧線BA上的點的縱坐標(biāo)。

性質(zhì)1：給定一條直線Y=tan α#8226;X在α≠0處穿過點S和D，YD1=tan α#8226;Rtan2α+1，YD2=-tan α#8226;Rtan2α+1。YD1，YD2是弧線BA上的點的縱坐標(biāo)。

證明：給定一條直線Y=tan α#8226;X在α≠0處穿過點S和D，并與弧線BA交于D點，所以得方程組：

原命題可證。

根據(jù)基于節(jié)點位置的路由算法的思想，只有在扇形BSA內(nèi)的節(jié)點(X，Y)才能轉(zhuǎn)發(fā)RREQ?，F(xiàn)在根據(jù)這個扇形的三條邊，對扇形內(nèi)的節(jié)點坐標(biāo)(X，Y)進行定位。

首先根據(jù)邊SB定位：

4 仿真環(huán)境與仿真結(jié)果

4.1 仿真環(huán)境

為了驗證算法的優(yōu)越性，選擇NS—2作為仿真工具對該算法進行了仿真分析，仿真過程中將本算法和傳統(tǒng)的AODV算法進行了比較。

網(wǎng)絡(luò)拓撲結(jié)構(gòu)是一個節(jié)點隨機分布在1 000 m×1 000 m的平面矩形區(qū)域的網(wǎng)絡(luò)模型，移動節(jié)點數(shù)為：50，100，150，200。節(jié)點隨機的以均勻分布在0～20 m/s之間的速度向任意方向移動。每個節(jié)點的無線接口帶寬為2 Mb/s，無線發(fā)射范圍(直接通信距離)為250 m。MAC層采用IEEE 802.11所規(guī)定的分布式協(xié)調(diào)功能(Distributed Coordination Function，DCF)來解決隱藏終端問題。在仿真中建立40條單向UDP連接，采用恒定比特率(Constant Bit Rate，CBR)數(shù)據(jù)流。其中，每個數(shù)據(jù)包長度為512 B，發(fā)包頻率為4 packets/s，仿真時間為600 s。

4.2 仿真結(jié)果

圖4給出了控制包的數(shù)量和網(wǎng)絡(luò)中節(jié)點數(shù)量之間的關(guān)系。在該算法中，控制包的數(shù)量隨著θ的值而改變，其中b=2a。在b＝60°的時候，改進后的協(xié)議比AODV協(xié)議減少了將近70%的控制包。當(dāng)目的節(jié)點和源節(jié)點是鄰居的時候，改進后的算法將更加有效。

圖4 控制包的數(shù)量和節(jié)點數(shù)量之間的關(guān)系

當(dāng)源節(jié)點從網(wǎng)絡(luò)層收到路由創(chuàng)建請求的時候，他需要花費時間去計算目的節(jié)點的位置。所以這種計算的時間應(yīng)該盡可能的小，以保證完成路由創(chuàng)建僅需要較小的延時。在該算法中，獲得目的位置的平均時間大約是1.4 ms，如圖5所示，這個時間是很低的。

5 結(jié) 語

本文在基于蜂窩網(wǎng)和Ad Hoc混合網(wǎng)絡(luò)路由算法AODV_I的基礎(chǔ)上提出一種新的改進方案，這種方案與原路由算法相比減小了網(wǎng)絡(luò)中控制包的數(shù)量，提高網(wǎng)絡(luò)的[LL]效率。但是如果目的位置信息在一個特定的時間間隔內(nèi)都沒有能夠被源節(jié)點收到，就可判斷目的節(jié)點不能被定位，于是發(fā)送節(jié)點就只能通過原路由算法去建立路由，而不能達到真正節(jié)約網(wǎng)絡(luò)資源的目的。所以，該算法就如何能適用于更為復(fù)雜的網(wǎng)絡(luò)情況仍待繼續(xù)改進與提高。

圖5 獲得目的位置所需的延時

參考文獻

[1]鄭少仁，王海濤，趙志峰.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京:人民郵電出版社，2005.

[2]AODV homepage.http://moment.cs.ucsb.edu/AODV/aodv.html.

[3]李娜.Ad Hoc與蜂窩網(wǎng)融合關(guān)鍵性技術(shù)的研究[D].南京:南京郵電大學(xué)，2005.

[4]LI H.Performance Comparison of Ad Hoc and Cellular—Based Routing Algorithms in Multihop Cellular Networks[A].The 5th International Symposium on Wireless Personal Multimedia Communications(WPMC)，2002.

[5]Ananthapadmanabha R.Multi—hop Cellular Networks:The Architecture and Routing Protocols，Proc.PIMRC，2001.

[6]Lin Y D，Hsu Y C.Multihop Cellular:A New Architecture for Wireless Communication[A].in IEEE INFOCOM′2000:1 273—1 282.

[7]徐雷鳴，龐博，趙耀.NS與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社，2003.

[8]Li Mboil.Multihop Communications in Future Mobile Radio Networks[J].The 13th IEEE International Symposium on PIMRC′2002，2002(1):54—58.

作者簡介

楊晉寧 男，1980年出生，山西靈石人，桂林電子科技大學(xué)，研究生在讀。主要研究方向為無線通信。

段吉海 男，廣西桂林人，桂林電子科技大學(xué)，副教授。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。