黃波 張小華

摘 要： 移動自組織網(wǎng)絡(luò)（MANETs）是無基礎(chǔ)設(shè)施、由移動節(jié)點構(gòu)成的動態(tài)網(wǎng)絡(luò)。MANETs的移動特性給路由協(xié)議的設(shè)計提出挑戰(zhàn)。為此，以典型的按需路由（AODV）為基礎(chǔ)，提出基于鏈路穩(wěn)定的MANETs路由協(xié)議，記為LSR。首先，分析了AODV的路由過程和不足，再計算節(jié)點能量壽命和鏈路壽命，然后通過比較能量壽命和鏈路壽命，構(gòu)建候選轉(zhuǎn)發(fā)節(jié)點集，最后，從鏈路穩(wěn)定性角度，選擇下一跳轉(zhuǎn)發(fā)節(jié)點。實驗結(jié)果表明，提出的LSR協(xié)議降低了路由開銷，提升了吞吐量。與AODV相比，LSR協(xié)議的路由開銷降低了近50%，吞吐量提高了23%。

關(guān)鍵詞： 移動自組織網(wǎng)絡(luò)； 路由； 按需路由； 鏈路壽命； 穩(wěn)定鏈路； LSR協(xié)議

中圖分類號： TN915.05?34； TPT393 文獻標識碼： A 文章編號： 1004?373X（2018）17?0090?05

Abstract： The mobile Ad Hoc networks （MANETs） composed of mobile nodes act as the dynamic network without infrastructure， and its mobile characteristic challenges the design of routing protocol. On the basis of the typical Ad Hoc on?demand distance vector （AODV） routing， the stable link based MANETs routing protocol （LSR） is proposed. The routing process and deficiency of AODV are analyzed， and then the energy lifetime and link lifetime of the node are calculated. The candidate forwarding node set is constructed by comparing the energy lifetime with link lifetime. The next?hop forwarding node is selected in term of link stability. The experimental results show that the proposed LSR protocol can reduce the routing overhead and improve the throughput. In comparison with AODV， the routing overhead of LSR protocol is reduced by 50%， and the throughput is improved by 23%.

Keywords： MANETs； routing； on?demand routing； link lifetime； stable link； LSR protocol

0 引 言

節(jié)點的移動性是移動自組織網(wǎng)絡(luò)（Mobile Ad Hoc Networks，MANETs）[1?2]典型特性。由于節(jié)點自由移動，MANETs拓撲呈動態(tài)性變化。動態(tài)變化的拓撲對數(shù)據(jù)傳輸路徑提出挑戰(zhàn)。因此，路由技術(shù)成為MANETs的研究熱點。由于節(jié)點通信半徑有限，節(jié)點需要通過多跳傳輸方式才能將數(shù)據(jù)傳輸至目的節(jié)點。換而言之，數(shù)據(jù)包攜帶節(jié)點需要從鄰居節(jié)點中選擇某個節(jié)點作為下一跳節(jié)點，從而逐步建立完整的數(shù)據(jù)傳輸路徑。將尋找最優(yōu)的下一跳轉(zhuǎn)發(fā)節(jié)點的過程稱為路由發(fā)現(xiàn)。

現(xiàn)有的路由協(xié)議[4?5]主要有：表格驅(qū)動型、按需以及混合型三類。OLSR[3]，DSDV[4]就是典型的表格驅(qū)動型路由。按需路由協(xié)議典型的有AODV（Ad Hoc On?demand Distance Vector）[5]，ABR[6]。按需路由協(xié)議是指只有當節(jié)點需要傳輸數(shù)據(jù)時，才啟動路由發(fā)現(xiàn)工作?；旌闲吐酚墒侵附Y(jié)合表格驅(qū)動型和按需型特點的路由，典型的有ZRP[7]，CEDAR[8]。

這些協(xié)議的主要差異在于路由發(fā)現(xiàn)機制的不同。表格驅(qū)動型路由是預(yù)先建立路由表，然后依據(jù)查表傳輸數(shù)據(jù)包。按需路由是當節(jié)點需要傳輸數(shù)據(jù)包時，通過傳輸路由請求（Route REQuest，RREQ）控制包和路由回復(fù)（Route REPly，RREP）包建立路由。

文獻[9]提出了基于鏈路生存時間的改進路由協(xié)議（Enhanced Routing Protocol on Ad Hoc On?demand Distance Vector with Speed Variance， SV_AODV）。SV_ AODV路由協(xié)議計算每條鏈路的速度方差，再選擇速度方差最小的路徑傳輸數(shù)據(jù)，提高了鏈路的穩(wěn)定性。文獻[10]提出了AODV路由的改進協(xié)議AODV_D。AODV_D協(xié)議考慮了MAC層的節(jié)點競爭信息和接口隊列時延，降低了傳輸時延。文獻[11]提出AODV的優(yōu)化協(xié)議，基于單播和廣播結(jié)合策略，實現(xiàn)路由探測，通過降低廣播幀數(shù)量，增強路由穩(wěn)定性。文獻[12]提出了基于鏈路質(zhì)量的改進AODV協(xié)議，通過設(shè)定鏈路質(zhì)量閾值，丟棄鏈路質(zhì)量差鏈路，提高了路徑穩(wěn)定性。

本文研究了AODV協(xié)議的不足，然后針對移動自組織的特性，提出基于鏈路穩(wěn)定的MANETs路由協(xié)議，記為LSR（Link Stable Routing）。LSR協(xié)議充分考慮了MANETs的移動特性，從鏈路的穩(wěn)定性角度選擇下一跳轉(zhuǎn)發(fā)節(jié)點。實驗數(shù)據(jù)表明，提出的LSR協(xié)議能夠有效地提高數(shù)據(jù)包傳輸率，并降低了端到端傳輸時延。

1 AODV協(xié)議及問題描述

相對于其他反應(yīng)式路由，AODV協(xié)議具有一定的優(yōu)勢，具體而言，AODV協(xié)議是利用局部廣播發(fā)現(xiàn)路由。當節(jié)點需要傳輸數(shù)據(jù)包，它首先向鄰居廣播RREQ包。一旦是第一次收到RREQ包，鄰居節(jié)點就將自己信息加入RREQ包，并轉(zhuǎn)播，直到目的節(jié)點接收到RREQ包。

源節(jié)點與目的節(jié)點間可能存在多條路徑，因此，目的節(jié)點可能會收到來自不同路徑傳輸?shù)腞REQ包。目的節(jié)點就沿著傳輸RREQ包的路徑回復(fù)包，進而告知源節(jié)點，數(shù)據(jù)路徑通道已建立。

圖1顯示了AODV路由發(fā)現(xiàn)過程，其中圖1a）表述了RREQ的傳輸過程，圖1b）表示RREP的傳輸過程。具體而言，若源節(jié)點1需要傳輸數(shù)據(jù)包，就向鄰居節(jié)點廣播RREQ控制包，再由鄰居節(jié)點轉(zhuǎn)播，直到目的節(jié)點8接收到RREQ包。當目的節(jié)點8接收RREQ包后，就沿著傳輸RREQ包回復(fù)RREP包，即目的節(jié)點8沿著[8→5→2→1]向源節(jié)點1回復(fù)RREP控制包。源節(jié)點一旦接收了RREP，就意味著路由發(fā)現(xiàn)階段完成。

相比于其他反應(yīng)式路由，AODV路由具有一定的優(yōu)勢，如較低的控制開銷和按需特性[13]。但是對于移動自組織網(wǎng)絡(luò)而言，節(jié)點移動是一個重要特性。而傳統(tǒng)的AODV協(xié)議并沒有考慮到節(jié)點移動?；贏ODV的改進RAODV協(xié)議考慮了節(jié)點的移動性。此外，節(jié)點能耗也是一個必須考慮的因素。其中MAODV?X考慮了節(jié)點能耗問題，將節(jié)點能耗融入鏈路的穩(wěn)定性。然而，這些協(xié)議在路由發(fā)現(xiàn)過程中，只是單一考慮了節(jié)點移動或節(jié)點能耗。

為此，提出LSR協(xié)議。與傳統(tǒng)的AODV協(xié)議不同，LSR協(xié)議考慮了節(jié)點移動和能耗問題。同時，LSR協(xié)議不再建立從源節(jié)點至目的節(jié)點整條路徑，而是引用了基于位置路由的思想，從鏈路穩(wěn)定性角度選擇下一個轉(zhuǎn)發(fā)節(jié)點。

2 LSR協(xié)議

LSR協(xié)議中節(jié)點通過交互HELLO消息，獲取網(wǎng)絡(luò)拓撲信息，并且每個節(jié)點傳輸半徑為[R]，覆蓋范圍為圓形。通過交互節(jié)點的局部信息，可計算節(jié)點能量消耗率，再計算節(jié)點能量壽命，然后計算鏈路壽命，最后，計算鏈路的穩(wěn)定性。最終選擇最穩(wěn)鏈路傳輸數(shù)據(jù)包。整個LSR協(xié)議框圖如圖2所示。

2.1 能量消耗率

首先，計算節(jié)點的剩余能量。假定節(jié)點[i]的初始能量為[Ei]。若節(jié)點[i]每傳輸一個數(shù)據(jù)包所需的能量為[Ti]，每接收一個數(shù)據(jù)包所消耗的能量為[Rk]。因此，在時刻[t]，節(jié)點[i]的剩余能量[REit]為：

2.2 鏈路的穩(wěn)定性

2.3 下一跳轉(zhuǎn)發(fā)節(jié)點

假定源節(jié)點[S]需要轉(zhuǎn)發(fā)數(shù)據(jù)包，據(jù)此，節(jié)點[S]先向其鄰居節(jié)點廣播RREQ包，其包含了節(jié)點速度和位置。鄰居節(jié)點接收RREQ后，分別依據(jù)式（3）和式（9）計算能量壽命和鏈路穩(wěn)定性，并將這些信息載入RREP，向源節(jié)點[S]回復(fù)RREP。

通過多次接收RREP后，源節(jié)點[S]就從鄰居選擇中選擇一個最合適的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。為此，源節(jié)點[S]選擇在節(jié)點能量壽命區(qū)間具有鏈路最穩(wěn)定的節(jié)點作為下一跳節(jié)點。

具體而言，假定源節(jié)點[S]的一跳鄰居節(jié)點集為[NS]。源節(jié)點[S]就分別比較一跳鄰居節(jié)點（假定節(jié)點[i∈NS]）的能量壽命與鏈路壽命。只有能量壽命大于鏈路壽命的節(jié)點才能作為候選轉(zhuǎn)發(fā)節(jié)點集[ψS]，如式（10）所示。反之，若能量壽命小于鏈路壽命，即數(shù)據(jù)在傳輸過程中，節(jié)點能量消耗殆盡，這將導(dǎo)致鏈路中斷。

2.4 路由發(fā)現(xiàn)流程

當源節(jié)點[i]需要向目的節(jié)點[d]傳輸數(shù)據(jù)包時，先向鄰居廣播RREQ控制包。接收了RREQ控制包后，首先檢測是廣播ID，若之前已接收過同樣的ID，則丟棄。否則進一步判斷自己是否是目的節(jié)點，如果是，就直接回復(fù)RREP控制包，否則就計算能量壽命和鏈路壽命，并將這些信息載入RREP，再向源節(jié)點[i]回復(fù)RREP控制包。源節(jié)點接收多個RREP包后，依據(jù)式（10）構(gòu)建一跳候選轉(zhuǎn)發(fā)節(jié)點集，然后再依據(jù)式（11）產(chǎn)生下一跳轉(zhuǎn)發(fā)節(jié)點，整個流程如圖3所示。

3 數(shù)值分析

3.1 仿真場景

為了更好地分析LSR協(xié)議性能，通過NS2建立實驗平臺。[N]個節(jié)點隨機分布于1 000×1 000區(qū)域，且以Random Waypoint作為節(jié)點的移動模型，移動速度為[?]，且[R=250] m，節(jié)點初始能量為1 873 J。每次實驗獨立重復(fù)50次，取均值作為最終實驗數(shù)據(jù)。仿真時間為800 s。

為了衡量LSR協(xié)議性能，選擇AODV，SV?AODV和AODV_D作為參照。同時考查路由開銷、吞吐量和端到端傳輸時延方面的性能。其中路由開銷是指每接收一個數(shù)據(jù)包所需的控制開銷；吞吐量是指單位時間內(nèi)平均每個節(jié)點所接收的數(shù)據(jù)量；端到端傳輸時延是指平均傳輸一個數(shù)據(jù)包所需的時間。

3.2 實驗數(shù)據(jù)

3.2.1 路由開銷

首先分析路由開銷隨節(jié)點數(shù)的變化情況，其中，[N]從50～200變化，且節(jié)點移動速度[?=10 m/s]，實驗數(shù)據(jù)如圖4所示。

從圖4可知，路由開銷隨節(jié)點數(shù)的增加而增加。這主要是因為：節(jié)點越多，網(wǎng)絡(luò)密度越大，信道資源競爭越激烈，提升了控制包的冗余數(shù)。此外，節(jié)點數(shù)越多，傳輸路徑的跳數(shù)可能也越多，這也增加了控制包數(shù)。與AODV，SV?AODV和AODV_D相比，LSR協(xié)議的路由開銷得到有效控制。

圖5分析了路由開銷隨節(jié)點移動速度的變化情況。其中節(jié)點數(shù)為150，節(jié)點移動速度為從0～20 m/s變化。從圖5可知：移動速度的加快，加速了拓撲變化，增強了路徑的不穩(wěn)定性，導(dǎo)致需頻繁地建立數(shù)據(jù)包傳輸路徑，最終增加了路由開銷；AODV協(xié)議的路由開銷最多，這主要是因為AODV采用泛洪機制建立路由；LSR路由開銷最少，原因在于LSR路由在建立路由時考慮了節(jié)點的移動問題，并且總是選擇最穩(wěn)定的路由傳輸數(shù)據(jù)包。

通過圖4，圖5實驗數(shù)據(jù)可知，與AODV，SV?AODV和AODV_D協(xié)議相比，提出的LSR協(xié)議能有效地控制路由開銷。原因在于SV?AODV協(xié)議采用固定概率轉(zhuǎn)播數(shù)據(jù)包，并沒有依據(jù)網(wǎng)絡(luò)信息決策是否轉(zhuǎn)發(fā)數(shù)據(jù)包。與SV?AODV協(xié)議相比，AODV_D協(xié)議的路由開銷得到控制，但仍高于LSR。

3.2.2 吞吐量

圖6，圖7分別描述了吞吐量隨節(jié)點數(shù)和節(jié)點移動速度變化情況。在圖6的實驗中，節(jié)點數(shù)[N]從50～200變化，且節(jié)點移動速度[?=10] m/s；而在圖7實驗中，[N]為150，且節(jié)點移動速度從0～20 m/s變化。

從圖6可知，節(jié)點數(shù)的增加降低了吞吐量。原因在于：節(jié)點數(shù)越多，網(wǎng)絡(luò)資源競爭越激烈，影響了數(shù)據(jù)傳輸?shù)牧鲿承?。與AODV，SV?AODV和AODV_D協(xié)議相比，LSR協(xié)議的吞吐量最高，比AODV_D協(xié)議提高了近30%。這主要歸功于LSR協(xié)議是基于鏈路穩(wěn)定性選擇下一跳轉(zhuǎn)發(fā)節(jié)點。

圖7的數(shù)據(jù)與圖6類似。節(jié)點移動速度的變化減少了網(wǎng)絡(luò)吞吐量，原因在于：移動速度的增加，加劇網(wǎng)絡(luò)拓撲變化，必然降低路徑穩(wěn)定性。盡管如此，LSR協(xié)議仍能保持較高的吞吐量。

3.2.3 端到端傳輸時延

圖8，圖9分別描述了端到端傳輸時延隨節(jié)點數(shù)和節(jié)點移動速度變化情況。在圖8的實驗中，節(jié)點數(shù)[N]從50～200變化，且節(jié)點移動速度[?=10] m/s；而在圖9實驗中，[N]為150，且節(jié)點移動速度從0～20 m/s變化。

由圖8可知，節(jié)點數(shù)的增加加大了端到端傳輸時延，原因在于：節(jié)點數(shù)的增加，加劇了網(wǎng)絡(luò)資源的競爭，破壞了數(shù)據(jù)傳輸?shù)牧鲿承浴膱D9可知，LSR協(xié)議的端到端傳輸時延最低，這主要是因為LSR協(xié)議在選擇下一跳轉(zhuǎn)發(fā)節(jié)點時，充分考慮了節(jié)點的移動速度及鏈路的穩(wěn)定性，增強了LSR協(xié)議對節(jié)點移動的強健性。

4 結(jié) 論

針對MANETs的數(shù)據(jù)傳輸問題，提出基于鏈路穩(wěn)定的MANETs路由協(xié)議LSR。LSR從節(jié)點能量和鏈路穩(wěn)定性出發(fā)，旨在選擇穩(wěn)定路徑傳輸數(shù)據(jù)包。依據(jù)節(jié)點移動以及能量消耗速度，計算能量壽命和鏈路壽命，再構(gòu)建候選轉(zhuǎn)發(fā)節(jié)點集，最后，擇優(yōu)選擇下一跳轉(zhuǎn)發(fā)節(jié)點。仿真數(shù)據(jù)表明，提出的LSR協(xié)議能夠有效地降低時延，并提高吞吐量。

參考文獻

[1] CHITRAXI R， URVIK U， TWINKLE P M. Simulation of VANET using ns?3 and SUMO [J]. International journal of advanced research in computer science and software engineering， 2014， 4（2）： 563?569.

[2] ANDREA G， GIANLUIGI F. Irresponsible AODV routing [J]. Vehicular communications， 2015， 3（2）： 47?57.

[3] EI W， BEN G， SAFA H. MOLSR： mobile?agent based optimized link state routing protocol [C]// 2015 International Wireless Communications and Mobile Computing Conference. Pisca?taway： IEEE， 2015： 355?360.

[4] PERKINS C E， BHAGWAT P. Highly dynamic （DSDV） for mobile computers routing [C]// Proceedings of 1994 the ACM SIGCOMM. New York： ACM， 2014： 234?244.

[5] LEE S J， BELDING E M， PERKINS C E. Ad Hoc on?demand distance?vector routing scalability [J]. ACM mobile computing and communications， 2012， 6（3）： 94?104.

[6] TOH C K. Associativity?based routing for Ad Hoc mobile networks [J]. Wireless personal communications， 2010， 4（2）：103?139.

[7] HAAS Z J， PEARLMAN M R. The performance of query control schemes for the zone routing protocol [J]. IEEE transactions on networking， 2001， 9（4）： 427?438.

[8] SINHA P， SIVAKUMAR R， BAHRGHAVAN V. CEDAR： a core extraction distributed Ad Hoc routing algorithm [J]. IEEE journal on selected areas in communications， 1999， 17（8）： 1454?1466.

[9] 曹文君，薛善良.一種適用于城市車載網(wǎng)的改進的AODV協(xié)議[J].計算機與現(xiàn)代化，2016，23（7）：98?103.

CAO Wenjun， XUE Shanliang. An improved AODV routing protocol for urban vehicular Ad Hoc networks [J]. Computer and modernization， 2016， 23（7）： 98?103.

[10] 劉大勇，趙春江.基于AODV的農(nóng)田無線傳感器網(wǎng)絡(luò)路由和休眠算法[J].微電子學與計算機，2015（10）：115?120.

LIU Dayong， ZHAO Chunjiang. A wireless sensor network routing and sleeping algorithm in agriculture based on AODV [J]. Microelectronics & computer， 2015（10）： 115?120.

[11] 蔡菁，朱余兵.一種基于AODV改進的城市車載自組網(wǎng)絡(luò)路由協(xié)議研究[J].計算機工程與科學，2013，35（1）：61?66.

CAI Jing， ZHU Yubing. An improved AODV routing protocol in urban vehicular ad hoc networks [J]. Computer engineering and science， 2013， 35（1）： 61?66.

[12] BUTT M R， AKBAR A H. LABILE： link quality?based lexical routing metric for reactive routing protocols in IEEE 802.15.4 networks [J]. Journal of supercomputing， 2012， 62（1）： 84?104.

[13] LEI Q， WANG Xiaoqing. Improved energy?aware AODV rou?ting protocol [C]// 2009 International Conference on Information Engineering. [S.l.： s.n.]， 2009： 18?21.

[14] HAFEEZ K， ZHAO L， LIAO Z， et al. Impact of mobility on VANETs′ safety applications [C]// 2010 IEEE Global Telecommunications Conference. Piscataway： IEEE， 2013： 1?5.

[15] ZHAO M， LI Y， WANG W. Modeling and analytical study of link properties in multi?hop wireless networks [J]. IEEE tran?sactions on communications， 2012， 60（2）： 445?455.