基于鏈路穩(wěn)定性的Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議仿真與分析*

周永塔

(廣東南華工商職業(yè)學(xué)院 教育技術(shù)與信息中心，廣東 廣州 510507)

0 引言

隨著社會(huì)的發(fā)展、無(wú)線(xiàn)技術(shù)的進(jìn)步，加上人們想要擺脫有線(xiàn)網(wǎng)路的束縛，進(jìn)行不受時(shí)空限制的自由通信，使得無(wú)線(xiàn)網(wǎng)絡(luò)及其相關(guān)技術(shù)得到了飛速發(fā)展?；ヂ?lián)網(wǎng)已發(fā)展為有線(xiàn)網(wǎng)絡(luò)和無(wú)線(xiàn)網(wǎng)絡(luò)組成的綜合網(wǎng)絡(luò)。根據(jù)無(wú)線(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)可以將其劃分為兩類(lèi)：有固定基礎(chǔ)設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò)和無(wú)固定基礎(chǔ)設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò)[1]。有固定基礎(chǔ)設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò)包含大量移動(dòng)節(jié)點(diǎn)(如移動(dòng)終端)和少量固定節(jié)點(diǎn)(如基站)，移動(dòng)節(jié)點(diǎn)依靠通信范圍內(nèi)的固定節(jié)點(diǎn)進(jìn)行相互之間的通信[2]。此類(lèi)網(wǎng)絡(luò)可以有效地利用現(xiàn)成的固定基礎(chǔ)設(shè)施(如基站)，在固定設(shè)施的覆蓋范圍內(nèi)進(jìn)行通信，但其有效通信也僅僅局限于固定設(shè)施的覆蓋范圍以?xún)?nèi)[3]。有固定基礎(chǔ)設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò)的典型代表有無(wú)線(xiàn)蜂窩網(wǎng)和無(wú)線(xiàn)局域網(wǎng)等。但面對(duì)某些特殊的應(yīng)用場(chǎng)景，有固定基礎(chǔ)設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò)將不能勝任[4]。相比傳統(tǒng)有線(xiàn)網(wǎng)絡(luò)和有固定基礎(chǔ)設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò)，Ad Hoc網(wǎng)絡(luò)以其無(wú)中心、自組織、動(dòng)態(tài)拓?fù)?、有限帶寬、有限能量等特點(diǎn)，使其在許多環(huán)境的通信應(yīng)用中有獨(dú)特的優(yōu)勢(shì)[5]。例如，在軍事、應(yīng)急領(lǐng)域，Ad Hoc網(wǎng)絡(luò)能滿(mǎn)足高靈活性、高抗毀性、高可靠性、高可擴(kuò)展性等要求；在個(gè)人通信領(lǐng)域，Ad Hoc可以實(shí)現(xiàn)如手機(jī)、Pad、電腦等個(gè)人移動(dòng)通信設(shè)備間的通信；在商業(yè)應(yīng)用流域，Ad Hoc網(wǎng)絡(luò)可以構(gòu)建家庭網(wǎng)絡(luò)、移動(dòng)計(jì)算以及移動(dòng)辦公等[6]。因此Ad Hoc網(wǎng)絡(luò)具有廣闊的應(yīng)用前景。

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

由于A(yíng)d Hoc網(wǎng)絡(luò)體系結(jié)構(gòu)和其自身特點(diǎn)，使得Ad Hoc網(wǎng)絡(luò)中的多播比有線(xiàn)網(wǎng)絡(luò)中的多播要更加復(fù)雜。多播路由協(xié)議有兩種典型的分類(lèi)方法，第一種方法是按照按需路由和表驅(qū)動(dòng)路由分類(lèi)；另一種是根據(jù)多播數(shù)的構(gòu)造方式將Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議分為四類(lèi)[7]：基于樹(shù)的多播路由協(xié)議、基于網(wǎng)的多播路由協(xié)議、無(wú)狀態(tài)的多播路由協(xié)議和混合多播路由協(xié)議。表1為幾種常見(jiàn)Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議的比較[8-9]。

表1 Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議比較

Ad Hoc網(wǎng)絡(luò)中多播路由協(xié)議的主要思想是用最小的冗余找到多播成員間的通信路徑，上述各種協(xié)議使用不同的方法來(lái)試圖達(dá)到這個(gè)目標(biāo)。

2 基于鏈路穩(wěn)定性的MAODV

Ad Hoc網(wǎng)絡(luò)具有其固有的特點(diǎn)：網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性造成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化、節(jié)點(diǎn)終端設(shè)備的個(gè)體差異以及節(jié)點(diǎn)間的無(wú)線(xiàn)鏈路環(huán)境受限等，因此Ad Hoc網(wǎng)絡(luò)中的路由變得復(fù)雜且網(wǎng)絡(luò)的維護(hù)開(kāi)銷(xiāo)也較大。為提高Ad Hoc網(wǎng)絡(luò)的路由綜合性能，本文提出了基于鏈路穩(wěn)定性的Ad Hoc網(wǎng)絡(luò)多播路由：將經(jīng)典的MAODV協(xié)議改進(jìn)為基于鏈路穩(wěn)定性的MAODV(Stability based MAODV,SMAODV)協(xié)議，SMAODV中提出了“HELLO響應(yīng)機(jī)制”和“主動(dòng)鏈路切換機(jī)制”，HELLO響應(yīng)機(jī)制用于收集測(cè)算鏈路穩(wěn)定性和主動(dòng)鏈路切換所需的相關(guān)數(shù)據(jù)。

2.1 報(bào)文和路由表擴(kuò)展

由于鏈路的穩(wěn)定性需要收集節(jié)點(diǎn)間的傳輸時(shí)延和節(jié)點(diǎn)的移動(dòng)速度等信息，因此將MAODV原有報(bào)文均添加了節(jié)點(diǎn)的移動(dòng)速度字段，將RREP報(bào)文還添加了鏈路穩(wěn)定性向量，將鄰居表和多播路由表進(jìn)行了擴(kuò)展，添加了HR報(bào)文。SMAODV主要包含以下六種報(bào)文：RREQ、RREP、MACT、GRPH、HELLO和HR[10]。以下是相關(guān)的六個(gè)基本定義。

定義1節(jié)點(diǎn)間的傳輸時(shí)延td(transmission delay)：節(jié)點(diǎn)A和節(jié)點(diǎn)B通信，A在t1s時(shí)刻給B發(fā)送信息，B在t1r時(shí)刻收到，并在t2s時(shí)刻給A發(fā)送信息，A在t2r時(shí)刻收到信息，則：

(1)

定義2節(jié)點(diǎn)間的傳輸時(shí)延差值Δtd：兩次相鄰的傳輸時(shí)延的差值，該值可能為負(fù)：

Δtd=tdnew-tdold

(2)

其中，tdnew表示最新計(jì)算出的傳輸時(shí)延，tdold表示前一次的傳輸時(shí)延。

定義3節(jié)點(diǎn)的移動(dòng)速度ms(move speed)：在節(jié)點(diǎn)發(fā)送信息時(shí)的移動(dòng)速度。

定義4節(jié)點(diǎn)的移動(dòng)速度差值Δms：某節(jié)點(diǎn)收到另一節(jié)點(diǎn)兩次相鄰的移動(dòng)速度的差值，該值可能為負(fù)：

Δms=msnew-msold

(3)

其中，msnew表示最新收到的節(jié)點(diǎn)移動(dòng)速度，msold表示前一次收到的節(jié)點(diǎn)移動(dòng)速度。

定義5節(jié)點(diǎn)間的穩(wěn)定性向量nv(nodes vector)：該向量是一個(gè)四元組(td，Δtds，ms，Δmss)，用于測(cè)算節(jié)點(diǎn)間的穩(wěn)定性，是后續(xù)鏈路穩(wěn)定性的基礎(chǔ)。其中Δtds表示節(jié)點(diǎn)間的傳輸時(shí)延差值Δtd的符號(hào)位，Δmss表示節(jié)點(diǎn)的移動(dòng)速度差值Δms的符號(hào)位。

定義6鏈路穩(wěn)定性向量lv(link vector)：該向量是一個(gè)四元組(TD，ΔTDS，MS，ΔMSS)，用于測(cè)算鏈路的穩(wěn)定性。

2.2 HELLO響應(yīng)機(jī)制

為了獲得用于測(cè)算鏈路穩(wěn)定性的鏈路穩(wěn)定性向量，首先需要獲得節(jié)點(diǎn)間的穩(wěn)定性向量，本文通過(guò)“HELLO響應(yīng)機(jī)制”來(lái)測(cè)算節(jié)點(diǎn)間的穩(wěn)定性。節(jié)點(diǎn)定期廣播HELLO消息，該HELLO消息中附帶自己的移動(dòng)速度ms和發(fā)送該消息的時(shí)間t1s。收到HELLO消息的節(jié)點(diǎn)則響應(yīng)HR消息，該HR消息中附帶自己的移動(dòng)速度ms、收到的HELLO消息中的t1s、接收到該HELLO消息的時(shí)間t1r和發(fā)送HR消息的時(shí)間t2s。接收到HR消息的節(jié)點(diǎn)，則根據(jù)接收到HR消息時(shí)間t2s和HR消息中附帶的t1s、t1r和t2s來(lái)計(jì)算自己與響應(yīng)節(jié)點(diǎn)間傳輸時(shí)延td，隨后更新鄰居表。節(jié)點(diǎn)更新鄰居表時(shí)將鄰居傳輸時(shí)延和節(jié)點(diǎn)的移動(dòng)速度設(shè)為測(cè)算出的td和HR消息中附帶的ms，如果節(jié)點(diǎn)間是首次進(jìn)行HELLO響應(yīng)機(jī)制，則將Δtds和Δmss均設(shè)為0；否則根據(jù)定義5，如果測(cè)算出的td小于鄰居表中已有的傳輸時(shí)延則將Δtds設(shè)為-1，大于則設(shè)為1，Δmss同理。通過(guò)HELLO響應(yīng)機(jī)制就完成了節(jié)點(diǎn)間的穩(wěn)定性向量的測(cè)算。

此外，本文將控制消息均加入了移動(dòng)速度，所以在收到控制消息時(shí)都類(lèi)似于“HELLO響應(yīng)機(jī)制”一樣更新鄰居表中的ms和Δmss。后文介紹多播樹(shù)的構(gòu)建和維護(hù)時(shí)就不再介紹鄰居表的維護(hù)。

2.3 多播樹(shù)的構(gòu)建

非多播樹(shù)成員想要加入多播組，首先在多播路由表(Multicast Route Table，MRT)中創(chuàng)建表項(xiàng)表明自己是組成員，然后廣播RREQ-J消息；多播樹(shù)成員想要加入多播樹(shù)，只需要將MRT中自己的身份改為多播組成員。節(jié)點(diǎn)通過(guò)組頭表(Group Leader Table，GLT)檢測(cè)組頭可達(dá)性。在RREQ-J的傳播過(guò)程中節(jié)點(diǎn)在單播路由表(Unicast Route Table，URT)中建立至請(qǐng)求的源節(jié)點(diǎn)的反向路由。多播樹(shù)成員具有相同或者更大的序列號(hào)的節(jié)點(diǎn)，收到RREQ-J則單播回復(fù)RREP-J。當(dāng)節(jié)點(diǎn)收到RREP-J時(shí)將發(fā)送該RREP-J消息的節(jié)點(diǎn)在鄰居表(Neighbor Talbe，NT)中對(duì)應(yīng)的td、Δtds、ms和Δmss取出，分別累加進(jìn)RREP-J消息的TD、ΔTDS、MS和ΔMSS，然后繼續(xù)進(jìn)行轉(zhuǎn)發(fā)。RREP-J沿RREQ-J傳播建立的反向路由發(fā)送到請(qǐng)求的源節(jié)點(diǎn)，RREP-J傳播過(guò)程中節(jié)點(diǎn)在MRT中建立至多播樹(shù)的正向路由。當(dāng)請(qǐng)求的源節(jié)點(diǎn)在請(qǐng)求等待時(shí)間RREP_WAIT _TIME內(nèi)，如果是首次收到RREP-J消息，則將其存入緩存Cache中；否則將收到的RREP-J與Cache中的對(duì)比，如果擁有更新的序列號(hào)或者序列號(hào)相同但跳數(shù)更小或者序列號(hào)和跳數(shù)均相同但穩(wěn)定性更好，則用新收到的RREP-J替換Cache中原有的。等待RREP_WAIT _TIME后向Cache中的RREP-J選擇的上游節(jié)點(diǎn)單播MACT-J消息進(jìn)行路由激活。每個(gè)收到MACT-J的節(jié)點(diǎn)在自己的MRT中將該MACT-J的發(fā)送節(jié)點(diǎn)標(biāo)明為新的下一跳。如果收到MACT-J的節(jié)點(diǎn)是多播樹(shù)成員節(jié)點(diǎn)則加入完成，否則繼續(xù)向上游轉(zhuǎn)發(fā)MACT-J。

如果請(qǐng)求的源節(jié)點(diǎn)在等待RREQ_RETRIES后仍未收到任何RREP-J，則意味著網(wǎng)絡(luò)中無(wú)該多播樹(shù)或網(wǎng)絡(luò)被分割，則該節(jié)點(diǎn)作為組頭開(kāi)始維護(hù)多播組序列號(hào)和多播樹(shù)。圖1描述了MAODV的路由過(guò)程。

圖1 MAODV路由過(guò)程

2.4 主動(dòng)鏈路切換機(jī)制

由于節(jié)點(diǎn)的移動(dòng)性可能會(huì)造成斷路，而斷路的修復(fù)過(guò)程將給網(wǎng)絡(luò)帶來(lái)較大開(kāi)銷(xiāo)，從而降低MAODV的整體性能。本文在測(cè)算節(jié)點(diǎn)間的穩(wěn)定性的基礎(chǔ)上，提出了主動(dòng)鏈路切換機(jī)制，進(jìn)一步提高SMAODV的整體性能。

如圖2所示過(guò)程，多播組成員節(jié)點(diǎn)2即將離開(kāi)多播樹(shù)成員節(jié)點(diǎn)A的信號(hào)覆蓋范圍，進(jìn)入多播樹(shù)成員節(jié)點(diǎn)B的信號(hào)范圍。當(dāng)多播組成員節(jié)點(diǎn)2離開(kāi)多播樹(shù)成員節(jié)點(diǎn)A的信號(hào)范圍后將會(huì)發(fā)起鏈路修復(fù)過(guò)程，經(jīng)過(guò)修復(fù)過(guò)程多播組成員節(jié)點(diǎn)2又會(huì)嫁接成為多播樹(shù)成員節(jié)點(diǎn)B的下游節(jié)點(diǎn)。然而如果此過(guò)程可以提前預(yù)見(jiàn)并作出相應(yīng)的處理便能有效減少鏈路斷開(kāi)的情況，從而降低鏈路修復(fù)過(guò)程造成的開(kāi)銷(xiāo)、降低丟包率等。通過(guò)對(duì)控制包報(bào)文和鄰居表的擴(kuò)展便能提前發(fā)現(xiàn)并主動(dòng)作出處理。主動(dòng)鏈路切換機(jī)制主要分為三個(gè)步驟：危險(xiǎn)節(jié)點(diǎn)(可能因移動(dòng)性造成斷路的節(jié)點(diǎn))發(fā)現(xiàn)、危險(xiǎn)節(jié)點(diǎn)監(jiān)控和鏈路切換。

圖2 主動(dòng)鏈路切換

(1)危險(xiǎn)節(jié)點(diǎn)發(fā)現(xiàn)。當(dāng)多播樹(shù)成員節(jié)點(diǎn)在自己的鄰居表中存在非多播表中的上游和下游的節(jié)點(diǎn)，且鄰居表中自己的上游節(jié)點(diǎn)的Δtds為1，非上游和下游多播樹(shù)成員節(jié)點(diǎn)的Δtds為-1，則自己成為危險(xiǎn)節(jié)點(diǎn)，進(jìn)入危險(xiǎn)節(jié)點(diǎn)監(jiān)控。

(4)

圖3 節(jié)點(diǎn)移動(dòng)時(shí)間測(cè)算

(3)鏈路切換。鏈路切換包括嫁接和剪枝過(guò)程。進(jìn)入鏈路切換的危險(xiǎn)節(jié)點(diǎn)首先進(jìn)行嫁接，從鄰居表中選擇非自己的上游和下游節(jié)點(diǎn)中Δtds為-1且td最小的多播樹(shù)成員節(jié)點(diǎn)，向其單播RREQ-J消息，收到RREQ-J的節(jié)點(diǎn)單播響應(yīng)RREP-J消息。危險(xiǎn)節(jié)點(diǎn)收到RREP-J響應(yīng)后，向原上游節(jié)點(diǎn)單播MACT-P消息開(kāi)始剪枝，將MRT中自己的上游節(jié)點(diǎn)改為發(fā)送RREP-J的多播樹(shù)成員節(jié)點(diǎn)并向其單播MACT-J消息進(jìn)行鏈路激活。

3 仿真與分析

3.1 仿真環(huán)境設(shè)定與性能指標(biāo)

本文采用NS2_2.30對(duì)MAODV和SMAODV進(jìn)行仿真實(shí)驗(yàn)，并用以下3個(gè)典型的衡量路由協(xié)議的技術(shù)指標(biāo)作為考察指標(biāo)。

(1)數(shù)據(jù)包轉(zhuǎn)發(fā)率(Packet Delivery Ratio)。在多播環(huán)境下，計(jì)算網(wǎng)絡(luò)中的數(shù)據(jù)包在目標(biāo)節(jié)點(diǎn)接收與應(yīng)收個(gè)數(shù)，不僅反映數(shù)據(jù)傳送的可靠性能，也反映路由在失效下的穩(wěn)定性、高效性和持續(xù)性。

(2)數(shù)據(jù)包平均端到端時(shí)延(Average End-to-End Delay of Packets)。計(jì)算數(shù)據(jù)包在源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的傳送時(shí)間，通過(guò)其可以反映網(wǎng)絡(luò)擁塞等因素。

(3)路由開(kāi)銷(xiāo)(Routing Overhead)。通過(guò)其可以反映在路由出現(xiàn)異常情況下控制包數(shù)與數(shù)據(jù)包數(shù)之間負(fù)載情況。

3.2 NS2仿真實(shí)現(xiàn)

SMAODV協(xié)議中的相關(guān)參數(shù)設(shè)定如表2所示。

表2 SMAODV參數(shù)

本文仿真實(shí)驗(yàn)中移動(dòng)節(jié)點(diǎn)的速度采用0 m/s，5 m/s，10 m/s，20 m/s和混合速度五種。其中前四種均可以使用NS2提供的拓?fù)鋱?chǎng)景生成工具setdest來(lái)隨機(jī)生成無(wú)線(xiàn)網(wǎng)的節(jié)點(diǎn)運(yùn)動(dòng)場(chǎng)景；但setdest不能滿(mǎn)足生成混合速度無(wú)線(xiàn)節(jié)點(diǎn)運(yùn)動(dòng)場(chǎng)景的需求，所以需要手動(dòng)編寫(xiě)腳本。TCL腳本代碼省略，setdest使用命令格式如下：

setdest -v <1> -n -p -M -t -x -y

or

setdest -v <1> -n -s -m -M -P -p -t -x -y

3.3 仿真結(jié)果與分析

仿真就數(shù)據(jù)包轉(zhuǎn)發(fā)率、數(shù)據(jù)包平均端到端時(shí)延和路由開(kāi)銷(xiāo)對(duì)比說(shuō)明MAODV和SMAODV運(yùn)行性能。

(1)多播組成員數(shù)對(duì)性能的影響。將多播數(shù)據(jù)發(fā)送源節(jié)點(diǎn)數(shù)設(shè)為1，將節(jié)點(diǎn)的移動(dòng)速度設(shè)為5。測(cè)試結(jié)果如表3所示。

表3 不同多播成員數(shù)對(duì)性能影響測(cè)試結(jié)果

SMAODV采用基于鏈路穩(wěn)定性的路由選擇方法以及主動(dòng)鏈路切換策略等，減少了控制消息的發(fā)送以及斷路發(fā)生的情況，路徑優(yōu)于MAODV僅根據(jù)跳數(shù)選擇的路徑，在數(shù)據(jù)包平均端到端時(shí)延體現(xiàn)出較高的性能。

(2)多播數(shù)據(jù)發(fā)送源節(jié)點(diǎn)數(shù)對(duì)性能的影響。將多播組成員數(shù)設(shè)為10，將節(jié)點(diǎn)的移動(dòng)速度設(shè)為5，測(cè)試結(jié)果如表4所示。

數(shù)據(jù)包轉(zhuǎn)發(fā)率隨著多播數(shù)據(jù)發(fā)送源節(jié)點(diǎn)數(shù)的增加而降低，同樣SMAODV在數(shù)據(jù)包轉(zhuǎn)發(fā)率上體現(xiàn)出高于MAODV的性能。

通過(guò)上述兩組實(shí)驗(yàn)可以得出結(jié)論：SMAODV在數(shù)據(jù)包轉(zhuǎn)發(fā)率和數(shù)據(jù)包平均端到端時(shí)延上都優(yōu)于MAODV，在路由開(kāi)銷(xiāo)上略低于MAODV，所以SMAODV在綜合性能上優(yōu)于MAODV。

表4 多播數(shù)據(jù)發(fā)送源節(jié)點(diǎn)數(shù)對(duì)性能影響測(cè)試結(jié)果

4 結(jié)論

本文對(duì)MAODV協(xié)議進(jìn)行改進(jìn)，提出了基于鏈路穩(wěn)定性的Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議SMAODV。該協(xié)議主要包括路由構(gòu)建和維護(hù)過(guò)程、主動(dòng)鏈路切換策略、HELLO響應(yīng)機(jī)制。通過(guò)大量的實(shí)驗(yàn)進(jìn)一步驗(yàn)證了SMAODV協(xié)議的綜合性能，說(shuō)明本文提出的基于鏈路穩(wěn)定性的Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議具有正確性、可行性和優(yōu)越性。