MANETs中基于節(jié)點移動度的虛連接的路由

丁穎　黃繼海

摘 要： 由于移動自組織網(wǎng)絡(luò)MANETs中節(jié)點的快速移動，使得維持源節(jié)點與目的節(jié)點間的通信路徑成為一項挑戰(zhàn)性工作。節(jié)點的高速移動導(dǎo)致通信鏈路頻繁斷裂。為此，提出基于節(jié)點移動度的虛連接的路由（MDVRP）。虛路由為一條動態(tài)的邏輯路由，其由一系列的特定地理區(qū)域構(gòu)成。每個區(qū)域內(nèi)的節(jié)點依據(jù)自己的移動度設(shè)置轉(zhuǎn)發(fā)數(shù)據(jù)包的定時器，移動度越小，具有優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)包權(quán)。MDVRP通過虛路由策略，在源節(jié)點與目的節(jié)點間建立了多條傳輸路通，每個節(jié)點能獨立選取下一跳轉(zhuǎn)發(fā)節(jié)點，并利用節(jié)點移動度，擇優(yōu)選取轉(zhuǎn)發(fā)數(shù)據(jù)包下一跳節(jié)點，從而提高鏈路的穩(wěn)定性。仿真結(jié)果表明，提出的路由協(xié)議在端到端傳輸時延、路由開銷以及數(shù)據(jù)包傳輸率性能均得到提高。

關(guān)鍵詞： 移動自組織網(wǎng)絡(luò)； 路由協(xié)議； 移動節(jié)點； 虛路由； 虛連接

中圖分類號： TN915?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2017）20?0067?05

Abstract： Since the node in mobile Ad Hoc networks （MANETs） moves fast， which makes the maintaining of communication routing between source node and destination node become a significant challenge， and results in frequently break of communication links， a routing of virtual connection based on node mobility degree， which is marked as MDVRP （mobility degree of node?virtual router protocol）. The virtual routing is a dynamically?created logical routing that is constructed with a series of particular geographical areas. The timers of forwarding data packet of nodes in each region are set according to their mobility degree. The smaller the mobility degree of node is， the earlier the priority of forward data packet obtains. The MDVRP is used to establish more transmission paths between source node and destination node. Each node is able to independently determine its next forwarding node according to the stability degree of the node， so as to improve the stability of the link. The simulation results show that the proposed MDVRP has good performance in term of end?to?end transmission delay， routing overhead and transmission ratio of delivered packet.

Keywords： mobile Ad Hoc network； routing protocol； mobile node； virtual routing； virtual connection

0 引 言

移動自組織網(wǎng)MANETs （Mobile Ad Hoc Networks）是由移動節(jié)點MNs（Mobile Nodes）自行移動構(gòu)成的網(wǎng)絡(luò)[1]。在MANETs中，無需任何硬件設(shè)備，移動節(jié)點MNs能夠相互通信，每個移動節(jié)點MN扮演路由（Router）角色。由于移動節(jié)點MNs自由移動，使得拓?fù)浣Y(jié)構(gòu)動態(tài)變化，這也是移動自組織網(wǎng)MANETs最顯著的特性[2]。這一特性給MANETs的路由技術(shù)提出挑戰(zhàn)。

依據(jù)是否面向連接，MANETs中現(xiàn)有的路由協(xié)議可分為面向連接（Connection?oriented）路由協(xié)議和非連接（Connection?less）路由協(xié)議[3]。在面向連接（Connection?oriented）路由協(xié)議中，在數(shù)據(jù)包傳輸前先建立邏輯連接（Logical connection），并且在數(shù)據(jù)傳輸?shù)恼麄€過程，保持連接的連通性。一旦某鏈路斷裂，連接就發(fā)生中斷，數(shù)據(jù)傳輸失敗，就需要重新建立連接，增加了路由開銷。AODV協(xié)議[4]是典型的面向連接路由協(xié)議。

相反，非連接路由協(xié)議在數(shù)據(jù)傳輸前無需預(yù)先建立連接[5?9]。每個數(shù)據(jù)包內(nèi)存在通往目的節(jié)點的路由信息，獨立選路。若某鏈路斷開，節(jié)點依據(jù)目的地址，再重新選擇路由。

為此，為了能更好應(yīng)對高速移動的環(huán)境，提出基于節(jié)點移動度的虛路由（Virtual router）的連接路由協(xié)議，記為MDVRP（Mobility Degree of Node?Virtual Router Protocol）。盡管MDVRP協(xié)議是面向連接的，但是在數(shù)據(jù)傳輸前建立的是虛連接，而不是物理連接。虛路由是關(guān)于特定地理區(qū)域的邏輯路由（logical router）。一個虛路由是由地理區(qū)域內(nèi)的一個或多個移動節(jié)點構(gòu)成。虛路由所在地理區(qū)域性內(nèi)的物理節(jié)點依據(jù)節(jié)點的移動度設(shè)置轉(zhuǎn)發(fā)數(shù)據(jù)包的定時器，移動度越小，定時器時長越短，即具有優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)包權(quán)。仿真結(jié)果表明，相比于AODV，提出的MDVRP在提出的路由協(xié)議端到端傳輸時延、路由開銷以及數(shù)據(jù)包傳輸率性能均得到顯著提高。endprint

1 MDVRP協(xié)議

現(xiàn)存的路由協(xié)議方案，在面對高速移動的環(huán)境時，均遭受嚴(yán)重的鏈路斷裂。在此，提出的MDVRP方案，其重點是預(yù)防通信鏈路的斷裂而不是重建已斷裂的通信路徑。

1.1 關(guān)鍵概念

1.1.1 虛路由

虛路由是關(guān)于特定地理區(qū)域的邏輯路由[10]。 一條虛路由是由一系列地理區(qū)域內(nèi)的一個或多個移動節(jié)點構(gòu)成，可形成多條數(shù)據(jù)傳輸通路。每個節(jié)點一跳通信范圍為一個地理區(qū)域，且相鄰地理區(qū)域之間允許重疊。如圖1所示，源節(jié)點S與目的節(jié)點D存在一條虛路由[r1→r2→r3→r4→r5]。其中[r1，r2，…，r5]表示地理區(qū)域，如圖1中的虛線圈所示。在每個地理區(qū)域內(nèi)存在一個或多個傳感節(jié)點。這些傳感節(jié)點以多跳方式向目的節(jié)點傳輸數(shù)據(jù)包。此外一條虛路由存在多條路徑，圖1描述了兩條路徑[S→a→b→c→e→f→g→h→][m→D，S→A→B→C→E→F→G→H→L→M→D。]

1.1.2 節(jié)點的移動度

移動是MANETs最顯著的特性。為了更好地描述這一特性，本文引入節(jié)點移動度MD（Mobility Degree）量化此特性，并利用移動度進(jìn)行路由發(fā)現(xiàn)和路由更新，進(jìn)而找到穩(wěn)定的虛路由。

1.2 路由請求

當(dāng)源節(jié)點需要向目的節(jié)點發(fā)送數(shù)據(jù)包時，源節(jié)點首先產(chǎn)生路由請求消息M_req（Route Request Message），其包含源節(jié)點ID號，再廣播路由請求消息M_req，鄰近的節(jié)點將收到M_req。盡管收到M_req的每個節(jié)點能夠簡單地轉(zhuǎn)發(fā)該M_req，但是為了避免了網(wǎng)絡(luò)風(fēng)暴，采用隨機(jī)延時（Probabilistic delay）技術(shù)[11]。致使接收到M_req每個移動節(jié)點隨機(jī)延時一段時間[T]，且[T∈0 ， Tmax]。[Tmax]表示最長的延時時間。在這段時間內(nèi)，節(jié)點監(jiān)聽是否有其他節(jié)點轉(zhuǎn)發(fā)M_req。如果這段延時未結(jié)束前，已有其他節(jié)點轉(zhuǎn)發(fā)了該M_req，那么該節(jié)點就不再轉(zhuǎn)發(fā)M_req。若沒有，節(jié)點就在延時結(jié)束后，將自己的ID號嵌入M_req再轉(zhuǎn)發(fā)。通過多跳轉(zhuǎn)發(fā)方式，目的節(jié)點最終收到M_req消息。此外，本文將轉(zhuǎn)發(fā)M_req消息的節(jié)點，稱為轉(zhuǎn)發(fā)節(jié)點RN（Reply Node）。

1.3 路由回復(fù)

一旦目的節(jié)點收到M_req消息，目的節(jié)點就產(chǎn)生路由回復(fù)消息M_rep（route reply Messages ）消息，并建立通信路由。M_rep消息包括源節(jié)點、目的節(jié)點的ID號、路由ID，以及轉(zhuǎn)發(fā)M_req消息的一系列的轉(zhuǎn)發(fā)節(jié)點，如圖3所示。 目的節(jié)點產(chǎn)生了M_req消息后，立即廣播M_req消息。位于M_req消息中的轉(zhuǎn)發(fā)節(jié)點RNs就識別該路由。

在傳遞M_req消息的過程，一些鄰居節(jié)點可能監(jiān)聽M_req消息。這些監(jiān)聽節(jié)點可加入通信路由，成為傳遞數(shù)據(jù)包的潛在的一個成員。因此，與轉(zhuǎn)發(fā)節(jié)點RNs一樣，監(jiān)聽節(jié)點也能夠沿著路由轉(zhuǎn)發(fā)數(shù)據(jù)包。對于任何路由中的移動節(jié)點，包括轉(zhuǎn)發(fā)節(jié)點RNs和監(jiān)聽節(jié)點，最終是否轉(zhuǎn)發(fā)數(shù)據(jù)包是依據(jù)它的移動度MD決定的，具有最小移動度MD的節(jié)點具有最先轉(zhuǎn)發(fā)數(shù)據(jù)包的權(quán)利。

1.4 數(shù)據(jù)包的轉(zhuǎn)發(fā)

一旦建立了通信路由，源節(jié)點就可沿著該路由向目的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包。源節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)包前，先在數(shù)據(jù)包前加載一個信息頭，該信息頭包涵源節(jié)點的ID、目的節(jié)點ID以及數(shù)據(jù)包ID、路由ID、移動度MD以及遍歷節(jié)點TNs（Traversed Nodes）區(qū)域。數(shù)據(jù)包ID域用于存儲源節(jié)點需要向目的節(jié)點發(fā)送的數(shù)據(jù)包標(biāo)識。移動度MD域用于存儲轉(zhuǎn)發(fā)了數(shù)據(jù)包節(jié)點的移動度。遍歷節(jié)點TNs是指已轉(zhuǎn)發(fā)了數(shù)據(jù)包的一系列節(jié)點。

一旦節(jié)點[i]接收到來自節(jié)點[j]的數(shù)據(jù)包，節(jié)點[i]首先檢查自己是否是該數(shù)據(jù)包的目的節(jié)點。若是，則不轉(zhuǎn)發(fā)該數(shù)據(jù)包，否則進(jìn)一步檢驗之前是否有接收過該數(shù)據(jù)包，若有，則不轉(zhuǎn)發(fā)該數(shù)據(jù)包，若沒有，節(jié)點[i]檢測是否在該路由中，若不在，也不轉(zhuǎn)發(fā)該數(shù)據(jù)包，如果在，節(jié)點[i]將依據(jù)自己的移動度，設(shè)置等待轉(zhuǎn)發(fā)數(shù)據(jù)包的定時器。定時器的時間[Times]與移動度成正比，如下：

式中：[MDi，t]表示節(jié)點[i]在時刻[t]的移動度；[Timesmax]表示定時器的最長時間；[?]表示下限取整。

如果在定時器定時完畢之前，節(jié)點[i]監(jiān)聽到其他節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)包，那么節(jié)點[i]就不轉(zhuǎn)發(fā)數(shù)據(jù)包，并將定時器置0。否則，等待定時器計時，當(dāng)計時完畢，節(jié)點[i]就立即轉(zhuǎn)發(fā)該數(shù)據(jù)包。節(jié)點[i]處理來自節(jié)點[j]的數(shù)據(jù)包具體流程如圖4所示。

1.5 路由更新

如果一些節(jié)點脫離了虛路由，就可能導(dǎo)致鏈路斷裂。為了降低鏈路斷裂概率，目的節(jié)點周期地向源節(jié)點發(fā)送路由更新消息M_Rup（Route Update Message）。M_Rup消息包含目的節(jié)點ID、源節(jié)點ID、路由ID以及目的節(jié)點從源節(jié)點接收到的最新數(shù)據(jù)包所遍歷的節(jié)點集。目的節(jié)點通過這些節(jié)點集將M_Rup消息轉(zhuǎn)發(fā)給源節(jié)點。一旦源節(jié)點接收到M_Rup消息，將丟失舊的虛路由，采用新的路由。

圖5描述建立新路由的過程。假定現(xiàn)存在一新虛路由，其由[r1→r2→r3→r4→r5]一系列區(qū)域構(gòu)成。一旦該虛路由有鏈路斷裂，目的節(jié)點就發(fā)送路由更新M_Rup消息。目的節(jié)點D注意到，最新收到的數(shù)據(jù)包是[S→a→b→c→e→f→g→h→m→D]路徑傳遞。因此，目的節(jié)點沿著[D→m→h→g→f→e→c→][b→a→S]向源節(jié)點傳遞M_Rup消息。在M_Rup消息經(jīng)[D→m→h→g→f→e→c→b→a→S]傳遞至源節(jié)點過程中，這些節(jié)點的鄰居節(jié)點偷聽到M_Rup消息，從而形成新的虛路由[R′1→R′2→R′3→R′4→R′5]，如圖5所示的粗線圈。一旦源節(jié)點接收到M_Rup消息，隨后的數(shù)據(jù)包就沿著最新虛路由轉(zhuǎn)發(fā)。注意到，路由更新過程，節(jié)點不需要周期地廣播beaconing消息，降低了路由開銷。endprint

2 系統(tǒng)仿真及性能分析

為了更好地評估提出MDVRP性能，采用GloMoSim進(jìn)行仿真[12]，并與AODV和SVR[13]進(jìn)行性能比較。選擇AODV和SVR的原因是在于：AODV是移動自組織網(wǎng)絡(luò)中最典型的路由協(xié)議，具有很好的參考價值；SVR（Static Virtual Router）是靜態(tài)的虛路由，虛路由是預(yù)先設(shè)定的，并且每個移動節(jié)點有虛路由分布圖。而提出的MDVRP是動態(tài)的虛路由，將MDVRP與SVR進(jìn)行比較，能夠更好地分析MDVRP性能。

仿真過程中，首先考慮[100×1 000]的仿真區(qū)域，傳感節(jié)點均勻分布于仿真區(qū)域，傳感節(jié)點通信半徑為133 m。采用Random Way point 移動模型[14]。在該模型中，每個節(jié)點隨機(jī)選擇一個目的節(jié)點進(jìn)行移動。仿真時間為15 min，具體的仿真參數(shù)如表1所示。

2.1 性能指標(biāo)

分析MDVRP性能時，主要考慮數(shù)據(jù)包傳輸率RPD（Ratio of Packets Delivered）、端到端傳輸時延EED（End?to?End delay）以及歸一化的路由開銷NRO（Normalized Routing Overhead）三個指標(biāo)：

（1） 數(shù)據(jù)包傳輸率RPD。指目的節(jié)點接收到的數(shù)據(jù)包與源節(jié)點發(fā)送的數(shù)據(jù)包之比，其反應(yīng)了路由協(xié)議傳輸數(shù)據(jù)包的能力。

（2） 端到端傳輸時延EED。表示數(shù)據(jù)包從源節(jié)點傳遞至目的節(jié)點所需的時間，反應(yīng)了路由協(xié)議傳輸數(shù)據(jù)包的速度；

（3） 歸一化的路由開銷NRO。表示目的節(jié)點每接收一個數(shù)據(jù)包所需的控制包數(shù)量，其反應(yīng)路由協(xié)議的效率以及可擴(kuò)展性。

2.2 仿真結(jié)果及分析

在仿真過程中，設(shè)置三類不同場景考查節(jié)點移動速度、節(jié)點密度以及仿真區(qū)域大小對路由協(xié)議的性能影響。

（1）移動速度。為了分析移動速度對路由協(xié)議的性能影響，在仿真過程中將節(jié)點移動速度從10～25 m/s變化。仿真結(jié)果如圖6所示。

從圖6可知，提出的MDVRP方案的數(shù)據(jù)包傳輸率RPD、端到端傳輸時延EED以及歸一化的路由開銷NRO均優(yōu)于AODV。具體而言，在RPD方面，MDVRP優(yōu)于AODV，與SVR類似。采用虛路由的MDVRP和SVR均能應(yīng)對節(jié)點的高速移動，達(dá)到高的數(shù)據(jù)包傳輸率。而EED方面，類似地，MDVRP和SVR均優(yōu)于AODV，并且MDVRP也優(yōu)于SVR。這主要是因為：SVR中的通信路由是由預(yù)先設(shè)定的虛路由構(gòu)成，而MDVRP采用動態(tài)虛路由，能夠更好地應(yīng)對節(jié)點的移動。在NRO方面，MDVRP和SVR均優(yōu)于AODV，但MDVRP略優(yōu)于SVR，原因在于MDVRP采用動態(tài)虛路由，降低鏈路斷裂的概率，而SVR采用預(yù)設(shè)的虛路由，難以應(yīng)對因節(jié)點移動而帶來的鏈路，提高了路由開銷。

（2） 節(jié)點密度。為了分析節(jié)點密度對路由協(xié)議的性能影響。在[100×1 000]的仿真區(qū)域內(nèi)的節(jié)點數(shù)從600～3 000變化，換而言之，仿真區(qū)域內(nèi)節(jié)點密度發(fā)生變化。仿真結(jié)果如圖7所示。

從圖7可知，節(jié)點密度的增加提高了路由開銷，并且對數(shù)據(jù)包傳輸率有消極影響，導(dǎo)致了更高的傳輸時延。這主要是因為節(jié)點密度增加，使得每條路由請求中涉及的節(jié)點數(shù)增加，增加了網(wǎng)絡(luò)擁塞概率。

具體而言，從圖7（a）和圖7（c）可知，隨著節(jié)點密度的增加，AODV采用了更多的控制數(shù)據(jù)包修復(fù)路由，但數(shù)據(jù)包傳遞率未得到提升。相反，隨著節(jié)點密度的增加MDVRP的路由開銷只是略有增加，并且仍保持高的數(shù)據(jù)包傳輸率。從圖7（b）和圖7（c）可知，在高密度區(qū)域，AODV的傳輸時延比MDVRP高出了6倍，路由開銷高出了20倍。此外，SVR和MDVRP的數(shù)據(jù)包傳輸率、路由開銷的性能類似，但是MDVRP的端到端傳輸時延優(yōu)于SVR。

（3） 仿真區(qū)域大小。為了分析仿真區(qū)域大小對路由協(xié)議的性能影響，設(shè)置4個仿真區(qū)域尺寸，并保持節(jié)點密度相等。4個區(qū)域尺寸分別為：[500 m×500 m]區(qū)域，內(nèi)有250節(jié)點；[1 000 m×1 000 m]區(qū)域，內(nèi)有1 000節(jié)點；[1 500 m×1 500 m]區(qū)域，內(nèi)有2 250節(jié)點；[2 000 m×2 000 m]區(qū)域，內(nèi)有4 000節(jié)點。仿真結(jié)果如圖8所示，圖8的橫坐標(biāo)中的500，1 000，1 500，2 000分別表示[500 m×500 m]區(qū)域、[1 000 m×1 000 m]區(qū)域、[1 500 m×1 500 m]區(qū)域、[2 000 m×2 000 m]區(qū)域。

從圖8可知，AODV難以維持長的路由。隨著仿真區(qū)域的擴(kuò)大，路由長度增加，路由斷裂的概率也成比率增加。由于不采用固定的hop?by?hop路由，相比于AODV，MDVRP僅以小的路由開銷的增加（見圖8（c））得到高的數(shù)據(jù)包傳輸率（見圖8（a））。隨著仿真區(qū)域的擴(kuò)大，MDVRP的時延略有增加，如圖8（b）所示。這主要因為，仿真區(qū)域的擴(kuò)大，增長了路由，相應(yīng)地，增長了數(shù)據(jù)包達(dá)到目的節(jié)點的時延。

此外，注意到圖8（b）和圖8（c），在[2 000 m×2 000 m]區(qū)域，MDVRP的端到端傳輸時延性能比AODV提高了3倍，路由開銷性能提高了近40倍。與AODV相比，SVR仍具有良好的性能，但是SVR的端到端傳輸時延仍劣于MDVRP。

3 結(jié) 語

本文針對移動自組織網(wǎng)絡(luò)MANETs的路由協(xié)議，提出MDVRP協(xié)議。MDVRP采用虛路由，使得源節(jié)點至目的節(jié)點間存在多條通信路徑，并依據(jù)節(jié)點移動度，擇優(yōu)選取數(shù)據(jù)包的轉(zhuǎn)發(fā)節(jié)點，提高鏈路的穩(wěn)定性，能夠有效地應(yīng)對節(jié)點的移動。

仿真結(jié)果表明，提出的MDVRP在端到端傳輸時延、數(shù)據(jù)包傳輸率以及歸一化的路由開銷明顯優(yōu)于AODV。

參考文獻(xiàn)

[1] KUMAR M， MISHRA R. An overview of MANET： history， challenges and applications [J]. Indian journal of computer science and engineering， 2012， 3（1）： 121?125.endprint

[2] CHLAMTAC I， CONTI M， LIU N. Mobile ad hoc networking： imperatives and challenges [J]. Ad Hoc networks， 2003， 1（1）： 13?64.

[3] HO A H， HO Y H， HUA K A. Handling high mobility in next?generation wireless Ad Hoc networks [J]. International journal of communication systems， 2010， 23（9）： 1078?1092.

[4] GUI C， MOHAPATRA P. A framework for self?healing and optimizing routing techniques for mobile ad hoc networks [J]. Wireless networks， 2008， 14（1）： 29?46.

[5] 洪棒，俞立，張貴軍.無線傳感網(wǎng)絡(luò)自適應(yīng)分布式聚簇路由協(xié)議[J].自動化學(xué)報，2011，37（10）：1197?1206.

[6] 羅娟，肖儀，盧真，等.基于網(wǎng)絡(luò)編碼的多播車載網(wǎng)絡(luò)路由算法研究[J].計算機(jī)研究與發(fā)展，2011，48（9）：1616?1622.

[7] PANICHPAPIBOON S， FERRARI G， TONGUZ O K. Connectivity of ad hoc wireless networks： An alternative to graph?theoretic approaches [J]. Wireless networks， 2010， 16（3）： 793?811.

[8] 夏梓峻，劉春鳳，趙增華，等.基于鏈路預(yù)測的VANET路由算法[J].計算機(jī)工程，2012，38（4）：110?114.

[9] KESTING A， TREIBER M， HELBING D. Connectivity statistics of storeand?forward intervehicle communication [J]. IEEE transactions on intelligent transportation systems， 2010， 11（1）： 172?181.

[10] PASCOE?CHALKE M， GOMEZ J， RANGEL V， et al. Route duration modeling for mobile Ad?Hoc networks [J]. Wireless networks， 2010， 16（3）： 743?757.

[11] YAN Gongjun， OLARIU Stephan. A probabilistic analysis of link duration in vehicular Ad Hoc networks [J]. IEEE transactions on intelligent transportation system， 2011， 12（4）： 1227?1237.

[12] ZENG X， BAGRODIA R， GERLA M. GlomoSim a library for parallel simulation of large?scale wireless network [C]// Proceedings of the Twelfth Workshop on Parallel and distributed simulation. [S.l.：s.n.]，1998： 154?161.

[13] HO Y H， HO A H， HUA K A. Connectionless protocol： a localized scheme to ad hoc network [J]. International journal of Ad Hoc and ubiquitous computing （IJAHUC）. [S.l.：s.n.]， 2007， 2（1）： 21?35.

[14] LEE J H， ERNST T， CHILMAKURTI N. Performance analysis of pmipv6 based network mobility for intelligent transportation systems [J]. IEEE transaction on vehicular technology， 2012， 61（1）： 23?32.endprint