基于Ad hoc 能量均衡的AODV 協(xié)議改進

屈長青 李玲香

（湖南科技學院 計算機與通信工程系，湖南 永州 425199）

1 引言

移動Ad Hoc 網(wǎng)絡(luò)是由一組帶有無線收發(fā)裝置的移動節(jié)點組成的一個多跳的臨時性自治系統(tǒng)，網(wǎng)絡(luò)中的節(jié)點主要靠電池供電，屬于一種能量受限節(jié)點，如果不考慮節(jié)點的能量，就很容易使某些節(jié)點成為主要的中間節(jié)點，從而使得這些節(jié)點過早的死亡，影響整個網(wǎng)絡(luò)的生存時間。根據(jù)移動Ad Hoc 網(wǎng)絡(luò)路由協(xié)議的特殊性，近年來國外學者提出了多種移動Ad Hoc 網(wǎng)絡(luò)路由協(xié)議，如DSDV[1]、DSR[2]、AODV[3]、ABR[4]、TORA[5]等。源頭性的研究性工作主要集中在2001 年以前，后續(xù)的成果多為對這些協(xié)議的改進。

目前，路由協(xié)議的研究仍然是移動Ad Hoc 網(wǎng)絡(luò)研究成果最集中的部分。基于節(jié)點能耗的節(jié)能算法備受研究者的關(guān)注，在節(jié)點能量受限的情況下，正在進行對節(jié)省能耗和均衡能耗的深入研究，將節(jié)點能量的使用情況轉(zhuǎn)化成數(shù)據(jù)通過控制信息傳輸，用節(jié)點的能耗情況作為最終路由選擇的準則等。文獻[6]提出了一種具有終端節(jié)點能量感知的路由協(xié)議EARP，在一定程度上實現(xiàn)了負載均衡，保護了低能量節(jié)點。文獻[7]應(yīng)用全球定位系統(tǒng)（GPS）提供的信息作為啟發(fā)式信息，以減少網(wǎng)絡(luò)維護的開銷，有效降低了通信延時，但同時，GPS 又增加了新的能耗。文獻[8]在AODV 協(xié)議的基礎(chǔ)上通過中間節(jié)點對鏈路平均能耗的估算來進行選路，對過度使用的中間節(jié)點進行了有效保護。

本文針對Ad hoc 網(wǎng)絡(luò)中移動節(jié)點能量受限的問題，綜合考慮節(jié)點剩余能量和節(jié)點能量消耗速率兩方面因素，對AODV協(xié)議進行了研究，提出了如下改進：1)改進選路機制，將節(jié)點剩余能量與數(shù)據(jù)傳輸能耗的比作為控制信息，根據(jù)不同的業(yè)務(wù)確定不同的比值，節(jié)點以“量力而行”或“盡力而為”的方式進行數(shù)據(jù)發(fā)送；2)改進Hello 機制，通過偵聽相鄰節(jié)點的有效發(fā)送來代替Hello 信息。

2 選路機制改進

改進選路機制，其目的是既要盡力保證AODV 路由協(xié)議的優(yōu)點，又要保證鏈路中主要的中間節(jié)點不至于過早失效，從而保護低能量節(jié)點，延長網(wǎng)絡(luò)生存時間。

設(shè)所有相鄰節(jié)點具有相同的覆蓋能力，每個節(jié)點的實時剩余能量為E(t)，節(jié)點能感知自己的剩余能量，業(yè)務(wù)數(shù)據(jù)傳輸能耗為E(d)，令節(jié)點剩余能量與數(shù)據(jù)傳輸能耗的比E(t)/ E(d)=K，以K 作為節(jié)點是否參與路由的控制信息。

考查實時業(yè)務(wù)RTT（Real Time Traffic） 和盡力而為BET（Best Effort Traffic） 兩類業(yè)務(wù)，協(xié)議約定，對于實時業(yè)務(wù)，K 取值K（rtt），對于盡力而為類業(yè)務(wù)，K 取值為K（bet）。

2.1 路由請求

將業(yè)務(wù)類型，節(jié)點數(shù)據(jù)傳輸能耗引入路由請求，路由請求（RREQ）消息格式如圖1。

圖1 . 改進的路由請求（RREQ）消息格式

改進的路由請求消息的格式增加標志位和字段：T（Traffic flag 業(yè)務(wù)類型標志）：標志置位則表示盡力而為業(yè)務(wù)。

Data Transmission Energy Consumption（數(shù)據(jù)傳輸能耗），節(jié)點轉(zhuǎn)發(fā)本次數(shù)據(jù)所要消耗的能量，即E(d)。

節(jié)點要發(fā)送數(shù)據(jù)時，首先檢查自己路由表中是否有可用的有效路由，若沒有現(xiàn)成可用路由，則向鄰居節(jié)點發(fā)送RREQ。

2.2 RREQ 處理和轉(zhuǎn)發(fā)

當一個非目標節(jié)點接收到一個新的有效 RREQ，查看 RREQ 中的標志位 T，以確定業(yè)務(wù)類型，查看Data Transmission Energy Consumption（數(shù)據(jù)傳輸能耗）字段，讀出數(shù)據(jù)傳輸能耗值E(d)，讀出自己的剩余能量E(t)，計算自己的K，對于實時業(yè)務(wù)，若K≤K（rtt）,或者對于盡力而為類業(yè)務(wù)，若K≤K（bet）, 那么這個節(jié)點會丟棄這個RREQ，不作任何操作。否則，節(jié)點將按AODV 協(xié)議對EERQ 進行處理和轉(zhuǎn)發(fā)。首先，該節(jié)點會將RREQ 消息內(nèi)的跳數(shù)加一，表明該RREQ 又跳過了一個中間節(jié)點。然后該節(jié)點使用最長前綴匹配法搜索到發(fā)起節(jié)點IP 地址的反向路由，如果有必要，這條路由會被創(chuàng)建，或者用RREQ 消息內(nèi)的Originator Sequence Number 來更新[9]。

2.3 路由回復

目標節(jié)點接收到有效RREQ 消息，忽略其中的標志位T 和Data Transmission Energy Consumption（數(shù)據(jù)傳輸能耗）字段，創(chuàng)建一條路由回復消息RREP；如果接收到有效RREQ 消息的中間節(jié)點，它到目的節(jié)點有一條有效路由，則可直接向發(fā)起節(jié)點發(fā)送RREP 完成路由發(fā)現(xiàn)過程。

RREP 一旦被創(chuàng)建，RREP 消息就將被送往通向發(fā)起路由詢問的節(jié)點的下一跳節(jié)點，這個節(jié)點由路由表里通向發(fā)起節(jié)點的路由表項給出。當RREP 被轉(zhuǎn)發(fā)回發(fā)起節(jié)點時，它里面的“跳數(shù)”逐跳加一，確保當RREP 到達發(fā)起節(jié)點時，往返跳數(shù)一致[9]。

3 Hello 機制改進

在AODV 中，活動路由中的節(jié)點通過廣播本地Hello 消息提供連接信息，每經(jīng)過HELLO_INTERVAL 毫秒，節(jié)點檢查它在過去的HELLO_INTERVAL 是否發(fā)出了一個廣播消息。如果沒有，就播出一個TTL = 1 的Hello 信息RREP，RREP 信息字段設(shè)置如下：

目的IP 地址：此節(jié)點的IP 地址。

目的序列號：此節(jié)點的最新序列號。

跳數(shù)：0。

生命期：ALLOWED_HELLO_LOSS * HELLO_INTERVAL。

每當一個節(jié)點從臨近節(jié)點收到一個Hello 消息，該節(jié)點應(yīng)該確保它與此臨近節(jié)點有一條活動的路由，如果沒有，則創(chuàng)建一條， 如果一條路由已經(jīng)存在，那么這條路由的生命期應(yīng)該增加至少ALLOWED_HELLO_LOSS * HELLO_INTERVAL 毫秒。

Ad Hoc 網(wǎng)絡(luò)的傳輸是基于同頻共享信道時分收發(fā)分配技術(shù)的，因此當節(jié)點處于有效發(fā)送時，在傳輸能力覆蓋范圍內(nèi)的相鄰節(jié)點都能夠接收或偵聽到該節(jié)點發(fā)送的信息，盡管它可能不做任何處理。AODV 協(xié)議中的Hello 消息獨立于業(yè)務(wù)范圍之外固定周期性地廣播，在網(wǎng)絡(luò)業(yè)務(wù)負載相對較重的情況下，會導致網(wǎng)絡(luò)傳輸效率下降，增加網(wǎng)絡(luò)負載，進而增加網(wǎng)絡(luò)時延和節(jié)點能耗。

對Hello 機制改進如下：取消獨立于數(shù)據(jù)業(yè)務(wù)之外固定周期性地廣播的Hello 消息，通過偵聽相鄰節(jié)點的有效發(fā)送來提供連接信息。在RREP、RERR 等控制消息及業(yè)務(wù)數(shù)據(jù)包中增加一個Hello 消息標志H，如有必要，增加Hello 消息中的目的IP 地址和目的序列號字段。通過定時器，H 每隔HELLO_INTERVAL 毫秒置位，以避免相鄰節(jié)點的頻繁處理，置位維持時間為ALLOWED_HELLO_LOSS * HELLO_INTERVAL 毫秒，即與原Hello 消息包的生命期一致。

節(jié)點偵聽相鄰節(jié)點的有效發(fā)送時，若發(fā)現(xiàn)標志位H 置位，則讀取在相鄰節(jié)點上發(fā)送的控制消息或數(shù)據(jù)包中的目的IP 地址和目的序列號字段值，按AODV 協(xié)議的Hello 消息機制進行處理。

節(jié)點處理算法如下：

Procedure Packet process

If（偵聽到的標志位H 置位）

Then （讀取相關(guān)信息）

Then （更新、建立路由）

Else （繼續(xù)偵聽）

4 結(jié)束語

研究改進基于能量均衡的路由，可以使節(jié)點在不影響網(wǎng)絡(luò)整體性能的前提下有更長的工作期，進而使整個網(wǎng)絡(luò)維持更長的生命期。實驗驗證本文的算法能滿足多種業(yè)務(wù)的傳輸要求又能均衡全局網(wǎng)絡(luò)節(jié)點能量消耗，并且能夠延長網(wǎng)絡(luò)的有效生命周期。進一步的研究工作重點是將本文提出的路由改正機制作進一步的深化研究，具體從如下幾個方面努力：

（1）在能量消耗和節(jié)點路由上做進一步客觀的、動態(tài)的均衡，對實時業(yè)務(wù)和盡力而為業(yè)務(wù)動態(tài)、合理地選擇相關(guān)閾值K（rtt）、K（bet），使網(wǎng)絡(luò)中的能量消耗更公平，負載更均衡；

（2）進一步均衡和減少路由建立的能量損耗和時間開銷；

（3）根據(jù)實際移動Ad Hoc 網(wǎng)絡(luò)的不同要求來提高協(xié)議某些方面的QoS 性能。

[1]Charles E Perkins. Highly dynamic destination-sequenced distance-vector routing for mobile computers.In: Proc ACMSIGCOMM’94 Conference, London, England,1994,234-244.

[2]Johnson D B.Routing in ad hoc networks of mobile hosts.In: Proc IEEE Workshop on Mobile Computing Systems and Applications,1994,158-163.

[3]C. E. Perkins and E. M. Royer, Ad hoc On-Demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA’99), New Orleans, LA, USA, February 1999:90-100.

[4]Toh C-K.Associativity based routing for ad hoc mobile networks. Wireless Personal Communication Journal. Special Issue on Mobile Networking&Computing Systems,1997,4(2):1-36.

[5]Park V,Corson M S.A highly adaptive distributed routing algorithm for mobile wireless networks.In:Proc IEEEINFOCOM’97,Kobe,Japan,1997,1405-1413.

[6]鄭石,吳偉強,張欽宇,張乃通.基于能量感知的Ad hoc 路由算法研究[J].通信學報,2012,(4):9-15.

[7]王安保,胡小明.基于GPS 的啟發(fā)式Ad hoc 路由算法研究[J].計算機應(yīng)用研究,2010,(12):4708-4710.

[8]REN P Y, FENG J, HU P et al, J. Energy saving ad-hoc on-demand distance vector routing for mobile ad-hoc NETworks[A].IEEEICC’09[C]. Dresden, Germany 2009,1-5.

[9][美]巴薩尼,等.移動Ad hoc 網(wǎng)絡(luò)[M].西安:西安交通大學出版社,2012.