基于地理位置的AODV路由協(xié)議改進(jìn)算法的研究與實(shí)現(xiàn)

安曉燕

摘 ?要：在AODV（Ad Hoc On demand Distance Vector）路由協(xié)議中，中間結(jié)點(diǎn)會向網(wǎng)絡(luò)中的其余結(jié)點(diǎn)廣播路由請求消息（RREQ），這樣會消耗網(wǎng)絡(luò)結(jié)點(diǎn)的大量能量?；谶@一缺點(diǎn)，本文設(shè)計了一種新的思想：中間結(jié)點(diǎn)不在隨意轉(zhuǎn)發(fā)RREQ數(shù)據(jù)包，而是通過限制轉(zhuǎn)發(fā)條件，減少數(shù)據(jù)包的不必要發(fā)送，最終使請求消息朝著目的結(jié)點(diǎn)的方向轉(zhuǎn)發(fā)。通過實(shí)驗(yàn)證明在請求消息發(fā)送數(shù)量和網(wǎng)絡(luò)中通信結(jié)點(diǎn)的存活率等性能，改進(jìn)后的算法有了很大的提高。

關(guān)鍵詞：MGeo-aodv;地理位置;能量消耗

中圖分類號： TP212.9 ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ?文章編號： 1673-1069（2016）30-157-2

0 ?引言

在源結(jié)點(diǎn)尋找路由信息時，中間結(jié)點(diǎn)會向全網(wǎng)廣播RREQ數(shù)據(jù)包，會導(dǎo)致結(jié)點(diǎn)的能量大量消耗[1]。許多研究人員提出基于地理位置的最短路徑算法[2][3]，基于地理位置的Geo-aodv[4]路由協(xié)議可以首先根據(jù)獲取的結(jié)點(diǎn)位置，限制轉(zhuǎn)發(fā)條件，減少中間結(jié)點(diǎn)請求消息的發(fā)送數(shù)量，節(jié)省了能量消耗，但是不能對之前通信結(jié)點(diǎn)的數(shù)據(jù)信息進(jìn)行更新[5]，基于Geo-aodv協(xié)議的缺點(diǎn)，本文設(shè)計了MGeo-aodv （Modified Geography Ad Hoc On demand Distance Vector）路由協(xié)議。

1 ?MGeo-aodv路由協(xié)議描述

網(wǎng)絡(luò)中的每一個通信結(jié)點(diǎn)通過GPS獲取自己的地理信息，其地理位置坐標(biāo)可以用（x，y，z）代表，x，y，z分別表示x軸，y軸，z軸，即三維坐標(biāo)系空間，這里假設(shè)網(wǎng)絡(luò)中所有通信結(jié)點(diǎn)都處于地球平面（z=0）。起初因?yàn)椴]有建立源結(jié)點(diǎn)到目的節(jié)點(diǎn)的路由信息，所以源結(jié)點(diǎn)會查找Geo路由表，如果在該路由表中沒有任何所需目的結(jié)點(diǎn)的地理位置信息，將轉(zhuǎn)發(fā)角設(shè)置成360。，即向整個網(wǎng)絡(luò)廣播RREQ;如果在Geo路由表中可以找到目的結(jié)點(diǎn)的地理位置信息，則將轉(zhuǎn)發(fā)角設(shè)置為90。。當(dāng)源結(jié)點(diǎn)在發(fā)送完路由請求消息后，在設(shè)定的時間范圍內(nèi)沒有收到路由回復(fù)信息（RREP），則源結(jié)點(diǎn)會重新發(fā)送RREQ，同時將轉(zhuǎn)發(fā)角設(shè)置為180。，如果在規(guī)定的時間還沒有收到RREP，依次將轉(zhuǎn)發(fā)角設(shè)置為270。，360。（全網(wǎng)廣播）。

如圖1所示，Source為源結(jié)點(diǎn)，Destination為目的結(jié)點(diǎn)，網(wǎng)絡(luò)中有三個中間結(jié)點(diǎn)，分別是NodeN1，NodeN2，NodeN3。NodeN1為上一跳結(jié)點(diǎn)，NodeN2為當(dāng)前轉(zhuǎn)發(fā)結(jié)點(diǎn)。當(dāng)轉(zhuǎn)發(fā)角為A1，只有NodeN1在搜尋范圍內(nèi)，因此會轉(zhuǎn)發(fā)RREQ;如果轉(zhuǎn)發(fā)角為A2時，只有NodeN1，NodeN2會發(fā)送RREQ，因?yàn)镹odeN3不在搜尋范圍內(nèi)，所以收到請求消息后會丟棄。

①Geo路由表的管理

Geo路由表中的項(xiàng)目主要包括網(wǎng)絡(luò)中所有通信結(jié)點(diǎn)的序號，地理位置坐標(biāo)及IP地址（用IPv4表示）。如果中間結(jié)點(diǎn)收到RREQ，會在Geo路由表中查找有無源結(jié)點(diǎn)的信息，如果沒有或Geo路由表的源結(jié)點(diǎn)序號小于路由請求消息中的序號，那么通信結(jié)點(diǎn)就會及時更新Geo路由表。

②計算搜尋區(qū)域

圖1中，假設(shè)NodeN2收到NodeN1轉(zhuǎn)發(fā)的RREQ信息后，結(jié)點(diǎn)NodeN2首先判斷θ，若θ小于轉(zhuǎn)發(fā)角的1/2，那么NodeN2轉(zhuǎn)發(fā)RREQ。θ的計算公式：

θ=cos-1 （1）

如圖2設(shè)α為轉(zhuǎn)發(fā)角，由圖可知結(jié)點(diǎn)NodeN2明顯已經(jīng)遠(yuǎn)離了目的結(jié)點(diǎn)，θ大于轉(zhuǎn)發(fā)角的一半，所以NodeN2不在轉(zhuǎn)發(fā)請求消息。如果上一跳通信結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)的歐式距離小于當(dāng)前結(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的歐式距離，那么我們也認(rèn)為請求消息的轉(zhuǎn)發(fā)已經(jīng)偏離了目的結(jié)點(diǎn)方向，該結(jié)點(diǎn)會丟棄請求消息。

<E：＼123＼中小企業(yè)管理與科技·下旬刊201610＼97-197＼114-2.jpg>

圖2 ?節(jié)點(diǎn)轉(zhuǎn)發(fā)情況

2 ?OPNET介紹

本文采用OPNET網(wǎng)絡(luò)仿真，OPNET是常用的網(wǎng)絡(luò)仿真軟件之一。

該仿真軟件使用離散事件驅(qū)動模擬機(jī)理對網(wǎng)絡(luò)模型的功能特性進(jìn)行仿真。常用的編輯器主要有：項(xiàng)目編輯器（Project Model）、節(jié)點(diǎn)編輯器（Node Model）和進(jìn)程編輯器（Process Model），三個編輯器分別對應(yīng)建模所需的三個層次模型。它涉及仿真研究的各個階段，包括模型設(shè)計、仿真、數(shù)據(jù)收集和數(shù)據(jù)分析。OPNET提供了三層建模機(jī)制，分為：網(wǎng)絡(luò)層、節(jié)點(diǎn)層和進(jìn)程層。分別對應(yīng)了工程編輯器、節(jié)點(diǎn)編輯器和進(jìn)程編輯器。

3 ?實(shí)驗(yàn)結(jié)果分析

3.1 構(gòu)建仿真環(huán)境

隨機(jī)在2000米×1500米區(qū)域內(nèi)放置了50個通信節(jié)點(diǎn)。表1為仿真環(huán)境參數(shù)，在該實(shí)驗(yàn)中，分別設(shè)置不同的通信結(jié)點(diǎn)數(shù)對Geo-aodv和MGeo-aodv兩個路由協(xié)議進(jìn)行了仿真比較。

表1 ?參數(shù)設(shè)置

<E：＼123＼中小企業(yè)管理與科技·下旬刊201610＼97-197＼114-表1.jpg>

3.2 實(shí)驗(yàn)結(jié)果分析

為了更好地對兩個協(xié)議的性能進(jìn)行比較，我們首先定義兩個參數(shù)的計算公式：

①結(jié)點(diǎn)存活率的計算

NSR= ?（2）

上式中，用NSR表示存活率，如果該值越大，則說明網(wǎng)絡(luò)中未耗盡能量的結(jié)點(diǎn)越多。n表示結(jié)點(diǎn)總數(shù)，a為能量耗盡結(jié)點(diǎn)的個數(shù)。

②請求消息（RREQ信息）發(fā)送數(shù)量的計算

N=（Ns（i）+Nr（i））（3）

N為網(wǎng)絡(luò)中傳輸?shù)恼埱笙⒖倲?shù)，n表示結(jié)點(diǎn)總數(shù)，Ns（i）和Nr（i）分別表示第i個結(jié)點(diǎn)發(fā)送和接收請求消息的數(shù)量。

如圖3所示，隨著網(wǎng)絡(luò)中通信結(jié)點(diǎn)數(shù)量的增多，路由請求消息的發(fā)送數(shù)量也會隨之增大。在MGeo-aodv算法的設(shè)計上，中間結(jié)點(diǎn)收到請求消息后會根據(jù)設(shè)置的轉(zhuǎn)發(fā)條件進(jìn)行判斷，滿足條件的結(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ，不滿足的結(jié)點(diǎn)不再轉(zhuǎn)發(fā)。所以與Geo-aodv協(xié)議相比，MGeo-aodv在請求消息數(shù)量上有較大的改善。

如圖4所示，MGeo-aodv協(xié)議中通信結(jié)點(diǎn)的存活率要遠(yuǎn)遠(yuǎn)高于Geo-aodv協(xié)議。在MGeo-aodv算法中，對于偏離了目的結(jié)點(diǎn)方向的轉(zhuǎn)發(fā)結(jié)點(diǎn)不再轉(zhuǎn)發(fā)請求消息，減少了數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸，避免了結(jié)點(diǎn)不必要的能量消耗。在不同的通信結(jié)點(diǎn)個數(shù)的網(wǎng)絡(luò)中，均體現(xiàn)了這一優(yōu)勢。

<E：＼123＼中小企業(yè)管理與科技·下旬刊201610＼97-197＼114-4.jpg>

圖4 ?節(jié)點(diǎn)存活率

4 ?小結(jié)

本文主要介紹了MGeo-aodv算法，中間結(jié)點(diǎn)根據(jù)轉(zhuǎn)發(fā)角判斷其是否在搜尋區(qū)域中，并計算到達(dá)目的結(jié)點(diǎn)的距離，然后和上一跳到達(dá)目的結(jié)點(diǎn)的距離進(jìn)行比較，如果小于則轉(zhuǎn)發(fā)請求消息。通過設(shè)置轉(zhuǎn)發(fā)條件，控制請求消息的發(fā)送數(shù)量，從而達(dá)到節(jié)省能量消耗的目的，最后通過OPNET仿真驗(yàn)證了該協(xié)議的有效性。

參 考 文 獻(xiàn)

[1] ?Chaitali Biswas Dutta，Utpal Biswas.An energy aware blackhole attack for multipath AODV[C].IEEE International Conference on Business and Information Management （ICBIM），2014：142-147.

[2] ?Zainab Senan Mahmood.The Directional Hierarchical AODV （DH-AODV） routing protocol for wireless mesh networks[C]. IEEE International Conference on Computing， Control， Networking， Electronics and Embedded Systems Engineering （ICCNEEE），2015：224-229.

[3] ?Wang， Li Y，Yang X Y.Energy-Efficient Localized Routing in Random Multihop Wireless Networks [J]. IEEE Transactions on Parallel and Distributed Systems， 2011， 22（8）： 1249-1257.

[4] ?Vasil Hnatyshin， Malik Ahmed，Remo Cocco，.A Comparative Study of Location Aided Routing Protocols for MANET [J]. IEEE International Conference on Wireless Days （WD）， 2011： 1-3.