劉永廣

(1.廣東輕工職業(yè)技術(shù)學(xué)院，廣東廣州 510300;2.中國電子科技集團(tuán)第七研究所，廣東廣州 510310)

0 引言

Ad hoc網(wǎng)絡(luò)是一種多跳、無中心的自組織網(wǎng)絡(luò)，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都是對等的。為了實(shí)現(xiàn)多跳尋址，源和目的節(jié)點(diǎn)需要借助其他節(jié)點(diǎn)進(jìn)行分組轉(zhuǎn)發(fā)。因此，一個(gè)高效的、適應(yīng)性強(qiáng)的路由算法是保證Ad hoc網(wǎng)絡(luò)性能的關(guān)鍵。

針對Ad hoc網(wǎng)絡(luò)的特點(diǎn)，研究人員提出了多種Ad hoc網(wǎng)絡(luò)路由協(xié)議。從這些協(xié)議的研究方向上來看，基本上可以分為兩類:基于拓?fù)涞穆酚伤惴ê突谖恢玫穆酚伤惴?，而大多?shù)研究以拓?fù)錇榛A(chǔ)來進(jìn)行，如Ad hoc按需距離矢量路由 (Ad hoc ondemand distance vector routing，AODV)，動(dòng)態(tài)源路由(dynamic source routing，DSR)等［1］，關(guān)于這些協(xié)議的優(yōu)缺點(diǎn)，在上述相關(guān)文獻(xiàn)中已有詳細(xì)的分析和對比，此處不再贅述。為了減少拓?fù)湫畔⒎职l(fā)的開銷，并能更好適應(yīng)Ad hoc網(wǎng)絡(luò)用于移動(dòng)場景的特點(diǎn)，研究人員開始關(guān)注位置信息在Ad hoc網(wǎng)絡(luò)路由算法中的應(yīng)用，并提出了一些有代表性的算法［2－6］，這些算法的研究焦點(diǎn)均集中于中間節(jié)點(diǎn)根據(jù)位置信息采用什么策略轉(zhuǎn)發(fā)數(shù)據(jù)包。一些算法采用了貪婪策略［3－4］，這些算法根據(jù)自己的標(biāo)準(zhǔn)在轉(zhuǎn)發(fā)范圍內(nèi)選擇一個(gè)最優(yōu)中繼節(jié)點(diǎn)，這種選擇的好處是根據(jù)算法的側(cè)重點(diǎn)可以有效地優(yōu)化某一方面的性能，但是由于存在局部優(yōu)化問題，如果遇到終結(jié)節(jié)點(diǎn)，算法陷入死鎖，雖然采取了恢復(fù)措施，但是往往導(dǎo)致性能降低且無法找到最優(yōu)路徑。一些算法采用了定向洪泛策略［5］，雖然這種算法設(shè)計(jì)簡單，但洪泛導(dǎo)致數(shù)據(jù)包被轉(zhuǎn)發(fā)次數(shù)增加，網(wǎng)絡(luò)額外開銷增加，降低了網(wǎng)絡(luò)吞吐量，增加了網(wǎng)絡(luò)丟包率。此外，當(dāng)節(jié)點(diǎn)移動(dòng)速度較大時(shí)，算法的性能嚴(yán)重降低。

1 受飛鳥遷徙啟發(fā)的路由協(xié)議(BFIRP)

文獻(xiàn)［7］發(fā)現(xiàn)了上述問題，并受到飛鳥遷徙規(guī)律［8］的啟發(fā)，提出了一種基于飛鳥遷徙規(guī)律的Ad hoc網(wǎng)絡(luò)路由算法協(xié)議(bird flight－inspired routing protocol，BFIRP)，該算法利用了飛鳥遷徙過程路徑選擇的規(guī)律，發(fā)現(xiàn)飛鳥在沿球面遷徙過程中，經(jīng)過連接球面上2點(diǎn)且以球心為圓心的大圓路徑是最節(jié)省能量的。該算法根據(jù)獲得的位置信息，設(shè)計(jì)了基于位置信息的確切性中繼節(jié)點(diǎn)選擇方法。該算法由于精確地選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)、有效地減少了路由開銷，使得網(wǎng)絡(luò)吞吐量獲得明顯提高，丟包率減少，網(wǎng)絡(luò)整體性能獲得提高。但是，該算法在設(shè)計(jì)和基于實(shí)際應(yīng)用上還存在缺陷:首先，該算法在實(shí)現(xiàn)上依靠一個(gè)有中心的位置服務(wù)來獲得其他節(jié)點(diǎn)的位置信息，而Ad hoc網(wǎng)絡(luò)本身是無中心網(wǎng)絡(luò)，增加了中心選擇過程;其次，對于一些應(yīng)用場景，比如戰(zhàn)場，提供位置服務(wù)的節(jié)點(diǎn)一旦被摧毀，該算法將不能正常計(jì)算;最后，由于該算法在后繼節(jié)點(diǎn)的選擇方向上是明確的，因此，會(huì)出現(xiàn)該方向(具有一定角度)上無中繼節(jié)點(diǎn)存在的情況，對于這種情況，該算法采用了向源端發(fā)送失敗錯(cuò)誤(failure error，F(xiàn)ERROR)消息的路由恢復(fù)方法，源端收到FERROR后，重新選擇方向。這種處理增加了網(wǎng)絡(luò)的額外開銷，并且由于重新開始路由選擇，導(dǎo)致部分報(bào)文延遲增大，甚至被丟棄。

針對以上所述飛鳥遷徙算法存在的問題，本文提出了一種改進(jìn)的基于飛鳥遷徙的Ad hoc網(wǎng)絡(luò)路由算法，新算法僅繼承了原算法的方向選擇策略，對原算法的關(guān)鍵技術(shù)進(jìn)行了重新設(shè)計(jì)，增加了新的報(bào)文和數(shù)據(jù)結(jié)構(gòu)，去掉了原來的FERROR報(bào)文，從而克服了原算法的缺陷，使網(wǎng)絡(luò)性能得以有效提高。

2 新算法關(guān)鍵技術(shù)

2.1 信標(biāo)報(bào)文的發(fā)送周期

針對該問題，本算法選擇一個(gè)節(jié)點(diǎn)偏離原來位置的距離作為是否發(fā)送信標(biāo)報(bào)文的度量，只有當(dāng)該距離超過一定門限時(shí)，才發(fā)送信標(biāo)報(bào)文，即

(1)式中:(Xc，Yc，Zc)為節(jié)點(diǎn)的當(dāng)前坐標(biāo);(Xo，Yo，Zo)為節(jié)點(diǎn)移動(dòng)前的坐標(biāo)，節(jié)點(diǎn)通過一個(gè)定時(shí)器周期性計(jì)算Δ值，當(dāng)Δ ＞Δmax時(shí)(Δmax為最大偏移門限)，節(jié)點(diǎn)發(fā)送信標(biāo)報(bào)文，并用節(jié)點(diǎn)的當(dāng)前坐標(biāo)(Xc，Yc，Zc)來更新 (Xo，Yo，Zo)。

更進(jìn)一步，如果僅考慮絕對移動(dòng)距離也是不合理的，因?yàn)樵撻T限其實(shí)和區(qū)域的大小及節(jié)點(diǎn)的密度有關(guān)系。在一個(gè)節(jié)點(diǎn)相對密集的區(qū)域，一個(gè)節(jié)點(diǎn)的移動(dòng)會(huì)對其他節(jié)點(diǎn)路徑選擇發(fā)生重要的影響。如圖1所示，圖1a和圖1b為2個(gè)同樣大小的區(qū)域，在圖1a中有3個(gè)節(jié)點(diǎn)，而在圖1b中有4個(gè)節(jié)點(diǎn)，在節(jié)點(diǎn)S產(chǎn)生到目的節(jié)點(diǎn)D的路由，虛線圓標(biāo)出了目的節(jié)點(diǎn)移動(dòng)的2個(gè)位置。由圖1a可以看到，節(jié)點(diǎn)D在d1距離內(nèi)移動(dòng)時(shí)，S的轉(zhuǎn)發(fā)方位都是不用變化的，D節(jié)點(diǎn)也不用發(fā)送信標(biāo)報(bào)文。在圖1b中，由于節(jié)點(diǎn)變得密集，從圖1b可以看出，當(dāng)節(jié)點(diǎn)D在轉(zhuǎn)發(fā)區(qū)域1移動(dòng)了d2距離后進(jìn)入轉(zhuǎn)發(fā)區(qū)域2，此時(shí)，節(jié)點(diǎn)1已經(jīng)無法做中繼，節(jié)點(diǎn)D應(yīng)該發(fā)送信標(biāo)報(bào)文。由圖1看出，d1顯然大于d2，所以如果在上述2種應(yīng)用模式中采用同一個(gè)門限值，則是不合理的，基于該問題，以下本文給出了新的信標(biāo)報(bào)文發(fā)送度量。

圖1 區(qū)域大小和節(jié)點(diǎn)數(shù)對發(fā)送周期的影響Fig.1 Influence of area size and node number on sending period

假設(shè)在長、寬、高分別為Lx，Ly，Lz的空間區(qū)域內(nèi)有n個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)服從均勻分布，并定義在3個(gè)方向上的節(jié)點(diǎn)間平均間距為dx，dy，dz，節(jié)點(diǎn)D的移動(dòng)方向?yàn)?α，β，γ)，則定義節(jié)點(diǎn)D發(fā)送信標(biāo)的度量為

2.2 應(yīng)急路由

如圖2所示，在原算法中，源節(jié)點(diǎn)S需要向目的節(jié)點(diǎn)D發(fā)送數(shù)據(jù)，經(jīng)過下一跳方向計(jì)算，并選擇具有大概率值的節(jié)點(diǎn)2作為下一跳中繼節(jié)點(diǎn)，節(jié)點(diǎn)2經(jīng)過下一跳計(jì)算形成自己的轉(zhuǎn)發(fā)區(qū)域，但該轉(zhuǎn)發(fā)區(qū)域內(nèi)并無中繼節(jié)點(diǎn)存在。此時(shí)，節(jié)點(diǎn)2會(huì)向源端S發(fā)送FERROR報(bào)文，S收到該報(bào)文后會(huì)重新調(diào)整方向，在其鄰居節(jié)點(diǎn)內(nèi)選擇6作為下一跳中繼。這個(gè)過程顯然是效率低下的，如果此時(shí)節(jié)點(diǎn)2能把報(bào)文直接轉(zhuǎn)到6，則省略了回傳FERROR報(bào)文和重新選路的過程，算法的效率會(huì)得以有效提高。

當(dāng)轉(zhuǎn)發(fā)區(qū)域無后繼節(jié)點(diǎn)時(shí)，原算法通過向源節(jié)點(diǎn)發(fā)送FERROR報(bào)文來通知源節(jié)點(diǎn)重新選擇新的方向和路由，這種方法增加了延遲。為克服算法這一弊端，我們利用信標(biāo)報(bào)文的信息生成一個(gè)基于距離矢量的應(yīng)急路由表，在一個(gè)節(jié)點(diǎn)知道其轉(zhuǎn)發(fā)方向內(nèi)的鄰居消失時(shí)，可以選擇另一可到達(dá)目的端的鄰居進(jìn)行轉(zhuǎn)發(fā)，具體處理過程和用到的數(shù)據(jù)結(jié)構(gòu)如下。

圖2 轉(zhuǎn)發(fā)區(qū)域無鄰居的情況Fig.2 Condition of no neighbor in forwarding area

每個(gè)節(jié)點(diǎn)在位置變化達(dá)到閾值Δmax或者路由表中有鄰居節(jié)點(diǎn)的位置更新時(shí)，均要發(fā)送攜帶變化信息的信標(biāo)報(bào)文，類似于AODV，每個(gè)節(jié)點(diǎn)通過信標(biāo)報(bào)文可以知道通過哪一個(gè)下一跳可以到達(dá)網(wǎng)絡(luò)中的其他目的節(jié)點(diǎn)，從而形成一個(gè)基于距離矢量的路由表，該路由表中允許對同一目的地存在多個(gè)路徑，以圖2中節(jié)點(diǎn)2的路由表為例，可看到如表1所示的路由表項(xiàng)。

表1 節(jié)點(diǎn)2的應(yīng)急路由表Tab.1 Emergency routing table of node 2

正常轉(zhuǎn)發(fā)情況下，節(jié)點(diǎn)只需利用鄰居節(jié)點(diǎn)的位置信息和目的節(jié)點(diǎn)的位置信息來計(jì)算轉(zhuǎn)發(fā)區(qū)域［7］，并不會(huì)用到該表。但是當(dāng)出現(xiàn)圖2的情況，節(jié)點(diǎn)3因?yàn)橐苿?dòng)出節(jié)點(diǎn)2的轉(zhuǎn)發(fā)區(qū)域，此時(shí)利用表1選擇一個(gè)下一跳轉(zhuǎn)發(fā)給節(jié)點(diǎn)6，不需要通過FERROR報(bào)文通告源節(jié)點(diǎn)S做重新選擇，節(jié)點(diǎn)6收到報(bào)文以后，繼續(xù)按照方向性選擇標(biāo)準(zhǔn)來計(jì)算轉(zhuǎn)發(fā)區(qū)域進(jìn)行轉(zhuǎn)發(fā)。

2.3 轉(zhuǎn)發(fā)中繼節(jié)點(diǎn)選擇

在本算法中，僅中繼節(jié)點(diǎn)的轉(zhuǎn)發(fā)策略，采用了原算法的思路，即

(4)式中:w1+w2+w3= 1;Ei為鄰居節(jié)點(diǎn)的能量;Emax為所有節(jié)點(diǎn)的最大能量值;dnd為鄰居節(jié)點(diǎn)和目的節(jié)點(diǎn)在大圓上的距離;did為本節(jié)點(diǎn)和目的節(jié)點(diǎn)在大圓上的距離;θ為鄰居節(jié)點(diǎn)偏離本節(jié)點(diǎn)和目的節(jié)點(diǎn)形成的大圓的角度。

參照文獻(xiàn)［7］，在下一節(jié)進(jìn)行仿真實(shí)驗(yàn)有能量參數(shù)時(shí)，選擇w1=w2=w3=1/3，其他選擇w1=w2=0.5，w3=0 。

2.4 Hello報(bào)文

在本算法的設(shè)計(jì)中，由于信標(biāo)報(bào)文不是周期性發(fā)送的，當(dāng)節(jié)點(diǎn)靜止或者移動(dòng)緩慢的時(shí)候，就不會(huì)產(chǎn)生信標(biāo)報(bào)文，而且，當(dāng)一個(gè)節(jié)點(diǎn)移走以后，其原來的鄰居收不到信標(biāo)報(bào)文，它會(huì)以為該鄰居處于靜止?fàn)顟B(tài)，因此，僅采用信標(biāo)報(bào)文來維持鄰居關(guān)系是不可行的。針對該問題，設(shè)計(jì)中增加一個(gè)Hello報(bào)文，該Hello報(bào)文為周期性的，但如果在下一個(gè)心跳報(bào)文發(fā)送時(shí)間到來之前發(fā)送了信標(biāo)報(bào)文，則會(huì)在當(dāng)前時(shí)間基礎(chǔ)上推遲一個(gè)周期作為下一次發(fā)送Hello報(bào)文的時(shí)間。該方法如圖3所示，第1個(gè)時(shí)間軸的豎線表示Hello報(bào)文的發(fā)送周期，第2個(gè)時(shí)間軸的豎線表示信標(biāo)報(bào)文的發(fā)送時(shí)間，由圖3可以看到，只要在一個(gè)Hello報(bào)文的發(fā)送周期內(nèi)發(fā)送了信標(biāo)報(bào)文，Hello報(bào)文的發(fā)送時(shí)間就一直會(huì)被推遲。也就是說，在這種情況下，信標(biāo)報(bào)文充當(dāng)了Hello報(bào)文的角色，只有在一個(gè)T時(shí)間內(nèi)沒有發(fā)送信標(biāo)報(bào)文的情況下，才由節(jié)點(diǎn)發(fā)送心跳報(bào)文，由圖3可以看到，這種設(shè)計(jì)有效地減少了Hello的維護(hù)開銷。

圖3 信標(biāo)報(bào)文對Hello報(bào)文發(fā)送時(shí)間的影響Fig.3 Influence of beacon packet on the time of sending Hello packet

3 性能評(píng)估

本節(jié)將通過仿真對算法的性能和參數(shù)進(jìn)行分析，主要對本文的改進(jìn)算法(I_BFIRP)和原算法BFIRP進(jìn)行比較，并同時(shí)和一種基于拓?fù)涞穆酚伤惴ˋODV［9］以及一種有代表性的基于位置信息的路由算法多跳轉(zhuǎn)發(fā)路由(multihop forward routing，MFR)［10］進(jìn)行比較。仿真在 NS2仿真環(huán)境下進(jìn)行，仿真參數(shù)如表2所示，節(jié)點(diǎn)在場景內(nèi)服從均勻分布，節(jié)點(diǎn)移動(dòng)速度服從［10，20］的均勻分布，Δmax=1。

表2 仿真環(huán)境參數(shù)設(shè)置Tab.2 Settings of simulation environment parameters

在以上條件下，首先對報(bào)文遞交的成功率進(jìn)行評(píng)估，如圖4所示。由圖4可以看出，隨著節(jié)點(diǎn)數(shù)的增加，網(wǎng)絡(luò)的動(dòng)蕩性加大，基于拓?fù)涞腁ODV路由協(xié)議由于拓?fù)渥儞Q，路由表變化頻繁，節(jié)點(diǎn)發(fā)送隊(duì)列溢出，使部分?jǐn)?shù)據(jù)報(bào)文被丟棄，從而導(dǎo)致報(bào)文丟包率降低。相反，基于位置的幾個(gè)路由協(xié)議，不需要維護(hù)路由表，只要在轉(zhuǎn)發(fā)方向上存在中繼節(jié)點(diǎn)，就能獲得準(zhǔn)確轉(zhuǎn)發(fā)，節(jié)點(diǎn)數(shù)的增加對這些算法的成功率影響不大。由圖4還可以看出，在節(jié)點(diǎn)數(shù)較少的時(shí)候，本文的改進(jìn)算法性能要明顯優(yōu)于原算法，這是因?yàn)樵诠?jié)點(diǎn)數(shù)稀疏時(shí)容易產(chǎn)生轉(zhuǎn)發(fā)區(qū)域無中繼節(jié)點(diǎn)的情況，由于本算法采用了應(yīng)急路由，可以迅速找到下一跳路由，而不需要轉(zhuǎn)發(fā)回源節(jié)點(diǎn)，所以成功率較高。當(dāng)節(jié)點(diǎn)數(shù)較多時(shí)，轉(zhuǎn)發(fā)方向上很少無中繼節(jié)點(diǎn)，本算法的應(yīng)急路由基本用不到，2個(gè)算法的性能趨于一致。另一方面，重新進(jìn)行路徑選擇也增加了端到端的延遲，這一點(diǎn)從圖5中可獲得驗(yàn)證。圖5是在移動(dòng)速度15 m/s時(shí)給出的仿真結(jié)果，在節(jié)點(diǎn)較稀疏時(shí)，相比原算法，本文的算法有較大的性能提升，但當(dāng)節(jié)點(diǎn)數(shù)增多時(shí)，優(yōu)勢就不再明顯。

為針對性評(píng)估改進(jìn)對算法的影響，圖6對2種算法在路由開銷方面的性能進(jìn)行了比較，由圖6可以看出，在350個(gè)節(jié)點(diǎn)情況下，由于移動(dòng)速度的增加，2種算法發(fā)送信標(biāo)報(bào)文的數(shù)量都明顯增加，但由于本文的算法采用了只有超出一定區(qū)域門限才發(fā)送信標(biāo)報(bào)文的策略，因此，信標(biāo)報(bào)文的發(fā)送數(shù)量明顯少于原算法，盡管增加了Hello報(bào)文，但絕大部分情況下，該報(bào)文被信標(biāo)報(bào)文代替，即使有發(fā)送，也是幾個(gè)字節(jié)來維持鄰居關(guān)系，可以忽略不計(jì)。

圖4 不同算法對成功率的影響Fig.4 Influence of different algorithms on success ratio

圖5 不同算法對端到端時(shí)延的影響Fig.5 Influence of different algorithms on end－to－end delay

圖6 2種算法的路由開銷比較Fig.6 Comparison of routing cost between two algorithms

圖7在350個(gè)節(jié)點(diǎn)、不同移動(dòng)速度情況下對端到端平均延遲做了比較，可以看到，由于采用了應(yīng)急路由策略，本算法的延遲要低于原算法，但隨著速度增加，如在20 m/s或更高時(shí)，本算法采用的應(yīng)急路由表由于拓?fù)渥儞Q太快而逐漸失去它的實(shí)用性，因此，當(dāng)移動(dòng)速度較大時(shí)，延遲方面的性能改進(jìn)就不太明顯，但是在拓?fù)渥兓惶珓×业那闆r下，本算法采用的策略還是對網(wǎng)絡(luò)性能的改進(jìn)有非常明顯的成效。圖8在多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)情況下對2個(gè)算法的能量消耗情況進(jìn)行了比較。由圖8可以看出，在絕大多數(shù)情況下，本文的算法由于節(jié)點(diǎn)減少報(bào)文發(fā)送數(shù)量，提高了路由恢復(fù)效率，從而能使節(jié)點(diǎn)獲得更多的剩余能量。

圖7 2種算法的端到端延遲比較Fig.7 Comparison of end－to－end delay between two algorithms

圖8 2種算法剩余能量的比較Fig.8 Comparison of residual energy between two algorithms

4 結(jié)論

本文對一種基于飛鳥遷徙原理的Ad hoc網(wǎng)絡(luò)組網(wǎng)算法進(jìn)行了研究，發(fā)現(xiàn)了算法中的缺點(diǎn)和不足，并針對這些不足提出了改進(jìn)算法，仿真結(jié)果表明，本文提出的改進(jìn)策略有效地提高了網(wǎng)絡(luò)的整體性能，而且，本文的部分研究結(jié)果也可適用于其他相關(guān)基于位置信息的路由算法性能改進(jìn)。

［1］SIVAKUMAR S，SUSEELA B，VARADHARAJAN R.A survey of routing algorithms for manet［C］//IEEE.Proceedings of International Conference on Advances in Engineering，Science and Management(ICAESM－2012).Nagapattinam，Tamil Nadu:IEEE Press，2012:625－640.

［2］DAY K，ARAFEH B，TOUZENE A，et al.A 3D grid position－based routing protocol formobile ad hoc networks［C］//IEEE.Proceedings of the International Conference on Computer and Communication Engineering.Kuala Lumpur:IEEE Press，2008:151－156.

［3］QABAJEH LK，KIAH LM，QABAJEH M M.A qualitative comparison of position－based routing protocols for ad hoc networks［J］.International Journal of Computer Science and Network，2011，9(2):131－140.

［4］CAO Y，XIE S.A position based beaconless routing algorithm formobile ad hoc networks［C］//IEEE.Proceedings of the IEEE International Conference on Communications，Circuits and Systems.Guangzhou，China:IEEE Press，2005:303－307.

［5］CHAN C，WARTY C，YU RW.Position based directional Ad－Hoc routing with space time diversity［C］//IEEE.Proceedings of Global Humanitarian Technology Conference(GHTC).Seattle，WA:IEEE Press，2012:192－197.

［6］LIAOW H，SHEU JP，TSENG Y C.GRID:A fully location – aware routing protocol for mobile ad hoc networks［J］.Telecommunication Systems，2001，18(1－3):37－60.

［7］MISRA S，RAJESH G.Bird flight－inspired routing protocol formobile ad hoc networks［J］.ACM Transactions on Autonomous and Adaptive Systems，2011，6(4):25－44.

［8］QIU J.Ornithology:Flightof the navigators［J］.Nature，2005，437(7060):804－806.

［9］PERKINSC E，ROYER E M.Ad hoc On－Demand Distance Vector(AODV)Routing［EB/OL］.(2003－07－01)［2013－06－28］.http://www.ietf.org/rfc/rfc3561.txt.

［10］TAKAGIH，KLEINROCK L.Optimal transmission ranges for randomly distributed packet radio terminals［J］.IEEE Transactions on Communication，1984，32(3):246－257.

(編輯:王敏琦)