馮永亮

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

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

馮永亮

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

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

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

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

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

針對(duì)傳統(tǒng)分簇路由協(xié)議導(dǎo)致Ad Hoc網(wǎng)絡(luò)可擴(kuò)展性差的問(wèn)題，本文提出一種基于分層結(jié)構(gòu)的Ad Hoc分簇網(wǎng)絡(luò)路由協(xié)議，即在低級(jí)網(wǎng)絡(luò)層簇成員之間采用一種基于路由備份的AODV路由協(xié)議，而在高級(jí)網(wǎng)絡(luò)層簇頭之間間則采用基于表驅(qū)動(dòng)的DSDV路由協(xié)議。仿真實(shí)驗(yàn)結(jié)果顯示，改進(jìn)后的路由協(xié)議提高分組到達(dá)率，降低了端到端時(shí)延，提高網(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é)點(diǎn)劃分為若干個(gè)簇，每個(gè)簇包含一個(gè)簇頭和若干個(gè)簇成員。網(wǎng)絡(luò)簇間節(jié)點(diǎn)的通信通過(guò)高層的簇頭轉(zhuǎn)發(fā)完成，通信過(guò)程只需要一次或少數(shù)幾次轉(zhuǎn)發(fā)即可完成，分層結(jié)構(gòu)如圖1所示。分層結(jié)構(gòu)將網(wǎng)絡(luò)分為低級(jí)網(wǎng)絡(luò)層和高級(jí)網(wǎng)絡(luò)層。低級(jí)網(wǎng)絡(luò)層由簇內(nèi)普通成員構(gòu)成。高級(jí)網(wǎng)絡(luò)層由簇頭選舉算法選舉出的、綜合性能較好的的簇頭節(jié)點(diǎn)構(gòu)成。簇頭主要負(fù)責(zé)管理和維護(hù)簇內(nèi)節(jié)點(diǎn)，以及簇與簇之間的通信。相對(duì)低級(jí)網(wǎng)絡(luò)層，高級(jí)網(wǎng)絡(luò)層減少了由于節(jié)點(diǎn)移動(dòng)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)造成的影響，結(jié)構(gòu)較為穩(wěn)定，因此提高了網(wǎng)絡(luò)的可擴(kuò)展性。

相對(duì)于ZRP協(xié)議直接在平面結(jié)構(gòu)上劃分簇，新的分層結(jié)構(gòu)具備如下優(yōu)點(diǎn)：①節(jié)點(diǎn)的改變或移動(dòng)只影響到其所在簇的結(jié)構(gòu)，降低了對(duì)整個(gè)網(wǎng)絡(luò)拓?fù)涞挠绊?，減少了洪泛開(kāi)銷(xiāo)。②提高了網(wǎng)絡(luò)穩(wěn)定性，降低了由于節(jié)點(diǎn)變化造成的重路由發(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è)計(jì)

2.1基本設(shè)計(jì)思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5　端到端延時(shí)Fig.5End-to-end Delay

4　結(jié)束語(yǔ)

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

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

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

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

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

［5］徐文濤.一種移動(dòng)Adhoc網(wǎng)AODV路由協(xié)議的改進(jìn)方法［J］.計(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］王忠恒，張曦煌.移動(dòng)AdHoc網(wǎng)絡(luò)AODV路由協(xié)議的改進(jìn)［J］.計(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］梁龍.移動(dòng)AdHoc網(wǎng)絡(luò)中AODV路由協(xié)議的改進(jìn)［J］.電子測(cè)試，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］王海濤.移動(dòng)Adhoc網(wǎng)絡(luò)路由協(xié)議及其性能比較［J］.重慶郵電學(xué)院學(xué)報(bào)，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］沈奔.無(wú)線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稿件編號(hào)：201501037

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