屈長青 李玲香

（湖南科技學(xué)院 計算機(jī)與通信工程系，湖南 永州 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é)議的特殊性，近年來國外學(xué)者提出了多種移動Ad Hoc 網(wǎng)絡(luò)路由協(xié)議，如DSDV[1]、DSR[2]、AODV[3]、ABR[4]、TORA[5]等。源頭性的研究性工作主要集中在2001 年以前，后續(xù)的成果多為對這些協(xié)議的改進(jìn)。

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

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

2 選路機(jī)制改進(jìn)

改進(jìn)選路機(jī)制，其目的是既要盡力保證AODV 路由協(xié)議的優(yōu)點，又要保證鏈路中主要的中間節(jié)點不至于過早失效，從而保護(hù)低能量節(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 . 改進(jìn)的路由請求（RREQ）消息格式

改進(jìn)的路由請求消息的格式增加標(biāo)志位和字段：T（Traffic flag 業(yè)務(wù)類型標(biāo)志）：標(biāo)志置位則表示盡力而為業(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ā)

當(dāng)一個非目標(biāo)節(jié)點接收到一個新的有效 RREQ，查看 RREQ 中的標(biāo)志位 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 進(jìn)行處理和轉(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 路由回復(fù)

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

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

3 Hello 機(jī)制改進(jìn)

在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。

每當(dāng)一個節(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ù)的，因此當(dāng)節(jié)點處于有效發(fā)送時，在傳輸能力覆蓋范圍內(nèi)的相鄰節(jié)點都能夠接收或偵聽到該節(jié)點發(fā)送的信息，盡管它可能不做任何處理。AODV 協(xié)議中的Hello 消息獨(dú)立于業(yè)務(wù)范圍之外固定周期性地廣播，在網(wǎng)絡(luò)業(yè)務(wù)負(fù)載相對較重的情況下，會導(dǎo)致網(wǎng)絡(luò)傳輸效率下降，增加網(wǎng)絡(luò)負(fù)載，進(jìn)而增加網(wǎng)絡(luò)時延和節(jié)點能耗。

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

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

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

Procedure Packet process

If（偵聽到的標(biāo)志位H 置位）

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

Then （更新、建立路由）

Else （繼續(xù)偵聽）

4 結(jié)束語

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

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

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

（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]鄭石,吳偉強(qiáng),張欽宇,張乃通.基于能量感知的Ad hoc 路由算法研究[J].通信學(xué)報,2012,(4):9-15.

[7]王安保,胡小明.基于GPS 的啟發(fā)式Ad hoc 路由算法研究[J].計算機(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].西安:西安交通大學(xué)出版社,2012.