馮永亮

（西安文理學(xué)院數(shù)學(xué)與計算機(jī)工程學(xué)院，陜西西安710065）

一種基于分層結(jié)構(gòu)的Ad Hoc網(wǎng)絡(luò)分簇路由協(xié)議研究

馮永亮

（西安文理學(xué)院數(shù)學(xué)與計算機(jī)工程學(xué)院，陜西西安710065）

傳統(tǒng)Ad Hoc網(wǎng)絡(luò)分簇路由協(xié)議存在分組投遞率低的問題，論文提出一種基于分層結(jié)構(gòu)的分簇路由協(xié)議。高級網(wǎng)絡(luò)層采用基于備份路由的AODV協(xié)議，而低級網(wǎng)絡(luò)層則采用時延較小的DSDV協(xié)議。仿真結(jié)果顯示，改進(jìn)后的路由協(xié)議提高了分組投遞率，縮短了端到端時延。

Ad Hoc；AODV；簇；路由；協(xié)議

無線Ad Hoc網(wǎng)絡(luò)是由任意分布且隨機(jī)移動的節(jié)點通過自組織的方式構(gòu)建的一種無線通信網(wǎng)絡(luò)，廣泛應(yīng)用于軍事行動、環(huán)境監(jiān)測、醫(yī)療急救、搶險救災(zāi)等領(lǐng)域。其主要特征包括：無中心管理節(jié)點、節(jié)點雙重身份、拓?fù)鋭討B(tài)變化、自組織、多跳路由、鏈路帶寬受限、能量受限和安全性較差等［1］。

按照拓?fù)浣Y(jié)構(gòu)，Ad Hoc網(wǎng)絡(luò)可分為平面結(jié)構(gòu)和分層結(jié)構(gòu)［2］。平面結(jié)構(gòu)中所有節(jié)點都是對等的，節(jié)點之間往往存在多條路徑，可以根據(jù)網(wǎng)絡(luò)狀態(tài)參數(shù)選擇適當(dāng)?shù)穆窂健Ｆ矫娼Y(jié)構(gòu)的路由協(xié)議分為表驅(qū)動和按需驅(qū)動的路由協(xié)議。其中，表驅(qū)動路由協(xié)議包括DSDV、WRP、FSR等，按需驅(qū)動路由協(xié)議包括AODV、TORA、ABR、SSR等［3］。實踐證明，基于平面結(jié)構(gòu)的路由協(xié)議，健壯性、安全性比較強(qiáng)，但是隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，協(xié)議的性能會下降，網(wǎng)絡(luò)開銷越來越大［4］。因此，研究者尋求通過改變網(wǎng)絡(luò)的物理結(jié)構(gòu)從根本上解決平面結(jié)構(gòu)的擴(kuò)展性問題。于是，分層結(jié)構(gòu)應(yīng)運(yùn)而生，所謂分層結(jié)構(gòu)是指利用一定的策略將網(wǎng)絡(luò)節(jié)點劃分為若干個簇，每個簇包含一個簇頭和若干個簇成員。簇頭是通過算法選出，并負(fù)責(zé)簇內(nèi)節(jié)點以及簇間節(jié)點之間的數(shù)據(jù)通信。常見的基于分層結(jié)構(gòu)的路由協(xié)議包括ZRP、CBRP、CGRP、CHSR等。相對于平面結(jié)構(gòu)，分層結(jié)構(gòu)明顯減少了節(jié)點間路由的跳數(shù)，降低了路由延時，改善了網(wǎng)絡(luò)的擴(kuò)展性，但是也導(dǎo)致可擴(kuò)展性差等問題。

針對傳統(tǒng)分簇路由協(xié)議導(dǎo)致Ad Hoc網(wǎng)絡(luò)可擴(kuò)展性差的問題，本文提出一種基于分層結(jié)構(gòu)的Ad Hoc分簇網(wǎng)絡(luò)路由協(xié)議，即在低級網(wǎng)絡(luò)層簇成員之間采用一種基于路由備份的AODV路由協(xié)議，而在高級網(wǎng)絡(luò)層簇頭之間間則采用基于表驅(qū)動的DSDV路由協(xié)議。仿真實驗結(jié)果顯示，改進(jìn)后的路由協(xié)議提高分組到達(dá)率，降低了端到端時延，提高網(wǎng)絡(luò)可擴(kuò)展性。

1　Ad Hoc分層網(wǎng)絡(luò)結(jié)構(gòu)

如圖1所示，Ad Hoc分層網(wǎng)絡(luò)結(jié)構(gòu)按照一定的策略將網(wǎng)絡(luò)節(jié)點劃分為若干個簇，每個簇包含一個簇頭和若干個簇成員。網(wǎng)絡(luò)簇間節(jié)點的通信通過高層的簇頭轉(zhuǎn)發(fā)完成，通信過程只需要一次或少數(shù)幾次轉(zhuǎn)發(fā)即可完成，分層結(jié)構(gòu)如圖1所示。分層結(jié)構(gòu)將網(wǎng)絡(luò)分為低級網(wǎng)絡(luò)層和高級網(wǎng)絡(luò)層。低級網(wǎng)絡(luò)層由簇內(nèi)普通成員構(gòu)成。高級網(wǎng)絡(luò)層由簇頭選舉算法選舉出的、綜合性能較好的的簇頭節(jié)點構(gòu)成。簇頭主要負(fù)責(zé)管理和維護(hù)簇內(nèi)節(jié)點，以及簇與簇之間的通信。相對低級網(wǎng)絡(luò)層，高級網(wǎng)絡(luò)層減少了由于節(jié)點移動對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)造成的影響，結(jié)構(gòu)較為穩(wěn)定，因此提高了網(wǎng)絡(luò)的可擴(kuò)展性。

相對于ZRP協(xié)議直接在平面結(jié)構(gòu)上劃分簇，新的分層結(jié)構(gòu)具備如下優(yōu)點：①節(jié)點的改變或移動只影響到其所在簇的結(jié)構(gòu)，降低了對整個網(wǎng)絡(luò)拓?fù)涞挠绊懀瑴p少了洪泛開銷。②提高了網(wǎng)絡(luò)穩(wěn)定性，降低了由于節(jié)點變化造成的重路由發(fā)生的概率。③提高了網(wǎng)絡(luò)擴(kuò)展性，適合于大型網(wǎng)絡(luò)。

圖1　Ad Hoc網(wǎng)絡(luò)分層結(jié)構(gòu)Fig.1Hierarchical structure of the Ad Hoc network

2　基于分層結(jié)構(gòu)的分簇路由協(xié)議的設(shè)計

2.1基本設(shè)計思想

高級網(wǎng)絡(luò)層主要負(fù)責(zé)簇頭節(jié)點間的穩(wěn)定、高效的通信，由于簇頭節(jié)點的處理能力、存儲容量、傳輸速度、剩余能量等性能指標(biāo)都比較良好，簇頭改變概率相對低一些，因此，適合采用按需驅(qū)動路由協(xié)議AODV。本文設(shè)計一種基于備份路由的AODV，避免路由重新發(fā)現(xiàn)。低級網(wǎng)絡(luò)層指各個分簇內(nèi)部的網(wǎng)絡(luò)結(jié)構(gòu)，這種結(jié)構(gòu)易受到簇成員節(jié)點移動影響。因此考慮選擇實時性強(qiáng)、路由發(fā)現(xiàn)時延小的表驅(qū)動路由協(xié)議DSDV。

2.2高級網(wǎng)絡(luò)層中簇頭路由協(xié)議的設(shè)計

在高級網(wǎng)絡(luò)層，源簇頭節(jié)點收到需要轉(zhuǎn)發(fā)的信息，首先會查找現(xiàn)有的路由表，如果發(fā)現(xiàn)存在到目標(biāo)簇頭節(jié)點的路由，則直接建立通信鏈路；若沒有發(fā)現(xiàn)到目標(biāo)簇頭節(jié)點的路由，則會廣播一個帶有目標(biāo)簇頭節(jié)點信息的路由分組RREQ到所有鄰居簇頭，鄰居簇頭會依次向周圍的簇頭繼續(xù)廣播這個路由分組，若此路由分組到達(dá)目標(biāo)簇頭節(jié)點，則停止廣播［5］。此時，目標(biāo)簇頭節(jié)點會沿著反向路由發(fā)送RREP，以便實現(xiàn)反向路由確認(rèn)，當(dāng)源簇頭節(jié)點收到反向裸游發(fā)送的RREP時，就能確定從源簇頭節(jié)點到目的節(jié)點之間的路由鏈路，從而實現(xiàn)簇頭間的通信。

由于AODV路由協(xié)議一般只維護(hù)路由表中的一條到指定目標(biāo)節(jié)點的路由，若該路由失效，源節(jié)點需要重新進(jìn)行路由發(fā)現(xiàn)，帶來大量的路由負(fù)載，增加了網(wǎng)絡(luò)負(fù)荷。為了充分利用路由廣播的RREQ，避免浪費路由資源，本文設(shè)計出目標(biāo)簇節(jié)點收到RREQ后，按不同路徑回復(fù)兩個RREP，對于已經(jīng)存在目標(biāo)節(jié)點有效路由的中間節(jié)點收到RREQ后，只要有一個中間節(jié)點回復(fù)RREP給源節(jié)點即可。這樣，源簇頭節(jié)點可以收到兩個RREP，而將最先達(dá)到的RREP里保存的路由作為主路由，第二個達(dá)到的作為備份路由［6］。當(dāng)主路由斷裂或失效時，源節(jié)點可以不必發(fā)起路由請求，直接調(diào)用備份路由［7］?；趥浞萋酚傻腁ODV模型如圖2所示。從源簇頭節(jié)點A到目標(biāo)簇頭節(jié)點G存在兩條路徑：（A，B，C，G）和（A，D，E，F(xiàn)，G）。

圖2　基于備份路由的簇頭間AODV路由模型Fig.2AODV routing model between cluster heads based on backup routing

2.3低級網(wǎng)絡(luò)層中簇成員路由協(xié)議的設(shè)計

低級網(wǎng)絡(luò)層由于受到簇成員影響較大，本文考慮采用按路由表驅(qū)動的、數(shù)據(jù)傳輸實時性強(qiáng)，路由發(fā)現(xiàn)延時小的DSDV路由協(xié)議。在DSDV中，每一個簇成員節(jié)點維護(hù)一個路由表，每個路由表項包括：目的地址、達(dá)到目的節(jié)點的度量、目的節(jié)點相關(guān)的序列號等，該序列號用來識別路由的新舊，作為路由更新和分組轉(zhuǎn)發(fā)的依據(jù)。各節(jié)點周期性的向鄰居節(jié)點通告其當(dāng)前的路由表，由于未采用洪泛方式，大大減少了通信的信息量［8］。基于DSDV路由協(xié)議的簇成員節(jié)點的路由表信息如圖3所示。

圖3　各簇成員節(jié)點路由表信息Fig.3Routing table information of each cluster member node

簇成員節(jié)點必須周期性交換路由信息，路由表的改變也可觸發(fā)路由更新。更新路由表有兩種方式：一種是部分更新，更新的消息中僅包含變化的路由部分，主要針對變化較慢的網(wǎng)絡(luò)；另一種是全部更新，主要用于變化較快的網(wǎng)絡(luò)。DSDV選擇使用序列號最高的路由，如果兩個路由具有相同的序列號，則選擇最優(yōu)的路由。

3　仿真結(jié)果實現(xiàn)及分析

為了對改進(jìn)的路由協(xié)議進(jìn)行評估，仿真環(huán)境采用了NS2，仿真場景為1 000 m×1 000 m里的100個移動節(jié)點，節(jié)點的通信范圍為200 m，節(jié)點停留時間分別為10 s，20 s，30 s。節(jié)點移動速度在0 m/s到20 m/s范圍內(nèi)均勻分布。仿真持續(xù)時間為120 s。

分組到達(dá)率是指目標(biāo)節(jié)點最終接收到的數(shù)據(jù)分組數(shù)目和源節(jié)點發(fā)送的數(shù)據(jù)分組數(shù)目的比值［9］。

從圖4可以看出，AODV、DSDV和改進(jìn)后的路由等三種路由協(xié)議呈現(xiàn)出不同的分組投遞率。DSDV協(xié)議采用表驅(qū)動路由方式，鏈接隨著節(jié)點的移動不斷發(fā)生變化，路由表中的信息大量失效，在鏈路較長時表現(xiàn)的更為明顯，分組會因為鏈路的失效而被丟棄，因此其分組到達(dá)率較低。AODV則表現(xiàn)出良好的投遞率，并且其穩(wěn)定性并未受網(wǎng)絡(luò)規(guī)模擴(kuò)大的影響。改進(jìn)后的路由協(xié)議綜合了前兩者的優(yōu)勢，將表驅(qū)動的旅游區(qū)域縮小，降低了路由表的信息量，降低了時延，提高了分組投遞率。同時，又吸收了AODV的穩(wěn)定性，但是，隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大，其性能有所下降。

圖4　分組到達(dá)率Fig.4Packet arrival rate

端到端分組平均延時是指數(shù)據(jù)分組成功從源節(jié)點到達(dá)目的節(jié)點平均所經(jīng)過的時間。端到端平均時延可以反映出網(wǎng)絡(luò)是否暢通，時延越小網(wǎng)絡(luò)越通暢［10］。

從圖5可以看出，在節(jié)點數(shù)小于20的情況下，DSDV表現(xiàn)出良好的性能，充分發(fā)揮出表驅(qū)動路由的優(yōu)勢。而AODV和改進(jìn)路由則表現(xiàn)出較大的延時，這是因為由于網(wǎng)絡(luò)節(jié)點數(shù)較少，不容易建立鏈路。隨著網(wǎng)絡(luò)規(guī)模不斷增大，AODV協(xié)議需要在每次發(fā)送數(shù)據(jù)包是才進(jìn)行路由查詢，端到端延時明顯增加。而改進(jìn)后的路由，由于節(jié)點數(shù)增加，高級網(wǎng)絡(luò)層簇頭節(jié)點按需進(jìn)行路由驅(qū)動，需要消耗時間，增加了時延，但相對于AODV表現(xiàn)出較低的延時。

圖5　端到端延時Fig.5End-to-end Delay

4　結(jié)束語

Ad Hoc網(wǎng)絡(luò)因組網(wǎng)靈活，適應(yīng)性強(qiáng)，所有有著廣泛的應(yīng)用前景，其路由協(xié)議一直是研究的熱點。文中針對Ad Hoc網(wǎng)絡(luò)分簇路由協(xié)議存在的分組投遞率低，端到端傳輸時延大等問題，提出了基礎(chǔ)分層結(jié)構(gòu)的路由方案，在高級網(wǎng)絡(luò)層的簇頭之間采用按需驅(qū)動，基于路由備份的AODV協(xié)議，而在低級網(wǎng)絡(luò)層采用實時性強(qiáng)，傳輸時延較小的DSDV協(xié)議。反震結(jié)果表明，改進(jìn)后的路由協(xié)議提高了分組達(dá)到率，減少了端到端傳輸延時，提高了Ad Hoc網(wǎng)絡(luò)的擴(kuò)展性。

［1］荊文禮.基于AdHoc網(wǎng)絡(luò)的AODV路由協(xié)議的研究與改進(jìn)［D］.無錫：江南大學(xué)，2013.

［2］門福軍.AdHoc網(wǎng)絡(luò)路由協(xié)議及性能研究［D］.西安：西安電子科技大學(xué)，2006.

［3］彭永祥.無線Adhoc網(wǎng)絡(luò)路由技術(shù)若干關(guān)鍵問題研究［D］.成都：電子科技大學(xué)，2013.

［4］倪旻明.移動網(wǎng)絡(luò)中分簇組網(wǎng)技術(shù)的研究［D］.北京：北京交通大學(xué)，2012.

［5］徐文濤.一種移動Adhoc網(wǎng)AODV路由協(xié)議的改進(jìn)方法［J］.計算機(jī)應(yīng)用與軟件，2013，30（3）：225-228. XU Wen-tao.Improvement of AODV routing protocol in Ad Hoc networks［J］.Computer Applications and Software，2013，30（3）：225-228.

［6］王忠恒，張曦煌.移動AdHoc網(wǎng)絡(luò)AODV路由協(xié)議的改進(jìn)［J］.計算機(jī)應(yīng)用，2010，30（2）：333-336. WANG Zhong-heng，ZHANG Xi-huang.Improvement of AODV routing protocol in mobile Ad Hoc network［J］.Jounal of Computer Applications，2010，30（2）：333-336.

［7］梁龍.移動AdHoc網(wǎng)絡(luò)中AODV路由協(xié)議的改進(jìn)［J］.電子測試，2010（4）：8-11，21. LIANG Long.Improvement of AODV routing protocol in mobile Ad Hoc networks［J］.Electronic Test，2010（4）：8-11，21.

［8］王海濤.移動Adhoc網(wǎng)絡(luò)路由協(xié)議及其性能比較［J］.重慶郵電學(xué)院學(xué)報，2002，14（4）：73-77. WANG Hai-tao.Routing protocols of Ad hoc network& theirs performance comparisons［J］.Journal of Chongqing University of Posts and Telecommunications，2002，14（4）：73-77.

［9］沈奔.無線AdHoc網(wǎng)絡(luò)中AODV路由協(xié)議的研究與改進(jìn)［D］.南京：南京郵電大學(xué)，2010.

［10］MAGNUS Frodigh，PER Johansson.WirelessAd hoc networking-the art of networkingwithout a network［J］.Ericsson Review，2000（4）：248-262.

Research based on the hierarchical structure of the Ad Hoc network clustering routing protocol

FENG Yong-liang
（School of Mathematics and Computer Engineering，Xi'an University of Arts and Science，Xi'an 710065，China）

The traditional Ad Hoc network clustering routing protocol has low packet delivery ratio problem，this paper proposes a clustering routing protocol based on hierarchical structure.The advanced network layer using AODV routing protocol based backup，and the lower network layer adopts a smaller delay DSDV protocol.The simulation results show that the improved routing protocol improves the packet delivery rate，Shortening the end to end delay.

Ad Hoc；AODV；cluster；route；protocol

TN915.04

A

1674-6236（2015）20-0086-03

2015-01-05稿件編號：201501037

馮永亮（1979—），男，陜西西安人，碩士，講師。研究方向：計算機(jī)網(wǎng)絡(luò)、物聯(lián)網(wǎng)。