周永塔

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

0 引言

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

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

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

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

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

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

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

2.1 報文和路由表擴展

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

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

(1)

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

Δtd=tdnew-tdold

(2)

其中，tdnew表示最新計算出的傳輸時延，tdold表示前一次的傳輸時延。

定義3節(jié)點的移動速度ms(move speed)：在節(jié)點發(fā)送信息時的移動速度。

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

Δms=msnew-msold

(3)

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

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

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

2.2 HELLO響應(yīng)機制

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

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

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

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

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

圖1 MAODV路由過程

2.4 主動鏈路切換機制

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

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

圖2 主動鏈路切換

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

(4)

圖3 節(jié)點移動時間測算

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

3 仿真與分析

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

本文采用NS2_2.30對MAODV和SMAODV進行仿真實驗，并用以下3個典型的衡量路由協(xié)議的技術(shù)指標作為考察指標。

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

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

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

3.2 NS2仿真實現(xiàn)

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

表2 SMAODV參數(shù)

本文仿真實驗中移動節(jié)點的速度采用0 m/s，5 m/s，10 m/s，20 m/s和混合速度五種。其中前四種均可以使用NS2提供的拓撲場景生成工具setdest來隨機生成無線網(wǎng)的節(jié)點運動場景；但setdest不能滿足生成混合速度無線節(jié)點運動場景的需求，所以需要手動編寫腳本。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ù)包平均端到端時延和路由開銷對比說明MAODV和SMAODV運行性能。

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

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

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

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

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

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

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

4 結(jié)論

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