一種基于節點位置的Ａｄ Ｈｏｃ和蜂窩混合網絡路由算法

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

關鍵詞：Ad Hoc；蜂窩網；AODV；GPS

中圖分類號：TN915 文獻標識碼：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”一詞來源于拉丁語，意思是“專用的、特定的為某一即將發生的特點目標、事件或局勢而不為其他的”，通常也把Ad Hoc網絡稱為“自組織網絡”或“無線多跳網絡”[1]。Ad Hoc網絡作為一種新的組網方式，和常見的有線固定網絡、蜂窩無線網絡以及無線局域網相比具有以下特點：Ad Hoc網絡是一個自組織、自啟動的無線移動網絡，他不需要中心基站的支持，沒有固定的網絡架構，具有多跳路由和移動終端的便攜性等。

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

為了實現兩種網絡的有機結合，須改進以前單一網絡的路由算法，以適應新的混合網絡。

2 混合網絡的路由算法AODV_I

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

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

擴展后的路由請求消息記為RREQ_I，結構如圖1所示。

圖1 擴展后的RREQ消息格式

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

擴展后的路由應答消息也在原有的路由應答消息上加入了全局地址解析標記(I_FLAG)。擴展后的路由應答消息記為RREP_I，其結構見圖2。

圖2 擴展后的RREP消息格式

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

3 AODV_I路由算法的改進

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

3.1 基于節點位置的路由轉發思想

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

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

文中將該“目的節點的方向”稱為“轉發區域”，即節點只向其轉發區域中的一跳鄰節點發送分組。為了限制轉發區域，源節點還要知道目的節點的位置信息。在這種轉發思想里，網絡中的每一個節點須周期性的向最近的基站登記自身的位置信息(節點的坐標)，在基站覆蓋范圍內的節點直接登記，范圍外的節點通過多跳依靠其他節點協助登記。基站維護一個位置表項來管理與之進行登記過的節點的位置和相關信息。

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

3.2 轉發區域的確定

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

圖3 轉發區域數學模型

很有必要知道一個節點是否能夠轉發控制包。首先，要介紹當XS≠XD且2α<90°時的搜索區域的性質。限制α的值是因為控制包只能朝著目的節點的方向轉發。

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

X軸的坐標)。

性質1可以用來決定弧線BA上的點的縱坐標。

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

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

原命題可證。

根據基于節點位置的路由算法的思想，只有在扇形BSA內的節點(X，Y)才能轉發RREQ。現在根據這個扇形的三條邊，對扇形內的節點坐標(X，Y)進行定位。

首先根據邊SB定位：

4 仿真環境與仿真結果

4.1 仿真環境

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

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

4.2 仿真結果

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

圖4 控制包的數量和節點數量之間的關系

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

5 結 語

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

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

參考文獻

[1]鄭少仁，王海濤，趙志峰.Ad Hoc網絡技術[M].北京:人民郵電出版社，2005.

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

[3]李娜.Ad Hoc與蜂窩網融合關鍵性技術的研究[D].南京:南京郵電大學，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與網絡模擬[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年出生，山西靈石人，桂林電子科技大學，研究生在讀。主要研究方向為無線通信。

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

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