任 智，周 舟，吳本源，陳加林

（重慶郵電大學通信與信息工程學院，重慶 400065）

0 概述

移動自組織網(wǎng)絡（MobileAd Hoc Network，MANET）是一種移動無線設備的自配置動態(tài)網(wǎng)絡［1］，其由一些可自由移動的節(jié)點構成，這些節(jié)點間通過無線連接進行通信，不需要任何基礎網(wǎng)絡架構。在MANET中，節(jié)點可以任意改變移動的方向和自身位置，使整個網(wǎng)絡呈現(xiàn)一種動態(tài)的網(wǎng)絡拓撲［2-3］。由于MANET路由協(xié)議能實現(xiàn)網(wǎng)絡的自我創(chuàng)建、組織和管理而無需人為參與，因此其被廣泛應用于車聯(lián)網(wǎng)、無人機和物聯(lián)網(wǎng)等領域［4-6］。

優(yōu)化鏈路狀態(tài)路由（Optimized Link State Routing，OLSR）協(xié)議是一種分布式主動路由協(xié)議［7］，其通過在一跳鄰居范圍內(nèi)選取多點中繼（Multipoint Relay，MPR）節(jié)點來減少拓撲控制消息的發(fā)送和轉發(fā)，進而通過HELLO 和拓撲控制（Topology Control，TC）消息發(fā)送來實現(xiàn)鏈路狀態(tài)和拓撲信息的全網(wǎng)分發(fā)［8］。OLSR 協(xié)議需要頻繁地交換控制信息以維持全網(wǎng)拓撲更新。相比動態(tài)源路由（Dynamic Source Routing，DSR）協(xié)議和無線自組網(wǎng)按需平面距離向量（Ad Hoc On-Demand Distance Vector，AODV）路由協(xié)議，OLSR 協(xié)議具有更高的網(wǎng)絡吞吐量和更低的端到端時延，因此適用于網(wǎng)絡規(guī)模大、節(jié)點數(shù)目多的大型密集網(wǎng)絡［9-11］。

為解決OLSR 協(xié)議拓撲發(fā)現(xiàn)和維護過程中開銷過大的問題，文獻［10］將MPR 集的選擇依賴條件擴展到三跳鄰居的本地數(shù)據(jù)庫，每個MPR 候選節(jié)點都被賦予新的信息來進行MPR 的選取，從而進一步減少TC 消息的冗余轉發(fā)。文獻［12-13］提出使用全局最優(yōu)MPR 集代替局部最優(yōu)MPR 集，優(yōu)先將已經(jīng)被其他節(jié)點選為MPR 的一跳鄰居節(jié)點選為MPR 節(jié)點，在不增加控制開銷的前提下減少網(wǎng)絡中TC 消息的數(shù)量。文獻［14］將傳統(tǒng)MPR 選擇和蟻群算法相結合，在MPR 集選取過程中添加信息素并引入補償-懲罰規(guī)則，將節(jié)點的當前移動狀態(tài)信息加入計算過程，有效地降低了MPR 集中的冗余。

在穩(wěn)定性方面，文獻［15］提出一種啟發(fā)式MPR選擇算法，節(jié)點間通過HELLO 消息交互移動狀態(tài)，優(yōu)先選擇移動性較小的節(jié)點作為MPR 節(jié)點，提升鏈路的保持時間。文獻［16］在HELLO 包中加入節(jié)點的位置信息，在MPR 選擇時考慮鏈路穩(wěn)定性，減少MPR 節(jié)點切換次數(shù)，增加路由表項的有效時間。PRAJAPATI 等［17］在MPR 集選擇過程中引入能量因素，優(yōu)先將剩余能量高的節(jié)點選為MPR 節(jié)點，在一定程度上延長網(wǎng)絡整體壽命，但選出的MPR 節(jié)點個數(shù)不是最少的。

文獻［18］基于OLSR 協(xié)議提出一種殘差預測優(yōu)化鏈路狀態(tài)路由（HTR-OLSR）協(xié)議，在相鄰節(jié)點的狀態(tài)信息未知時，引入殘差預測算法，從其他節(jié)點獲取所需信息，并將原始協(xié)議中的HELLO-Interval 和TC-Interval 分別下調到1 和3。通過頻繁獲取節(jié)點數(shù)據(jù)信息來降低節(jié)點能量級預測時的不準確性。該算法在一定程度上提高了節(jié)點壽命和網(wǎng)絡吞吐量，但增大了網(wǎng)絡開銷。

OLSR 協(xié)議通過廣播機制發(fā)現(xiàn)節(jié)點間鏈路信息和網(wǎng)絡拓撲可能產(chǎn)生的冗余重傳和無線電資源浪費等問題，SOUIDI 等［19］提出一種基于地理轉發(fā)規(guī)則的OLSR 協(xié)議。該協(xié)議使用節(jié)點的地理位置信息將網(wǎng)絡分為不同的虛擬區(qū)域，在廣播控制消息時避免其在不同區(qū)域間重復傳輸。該算法有效減少TC 消息的冗余傳播，但區(qū)域劃分和區(qū)域間通信增加了算法實現(xiàn)的復雜度。

本文提出一種針對優(yōu)化鏈路狀態(tài)路由的低開銷拓撲維護（Low Cost Topology Maintenance based on Optimized Link State Routing，LCTM-OLSR）算法。該算法去除MPR 集選取時存在的冗余，進而根據(jù)節(jié)點MPR 選擇集的變化情況，在穩(wěn)定量與變動量之間截取最小量作為TC 消息內(nèi)容進行發(fā)送。在此基礎上，利用歷史變動信息動態(tài)調整TC 消息的發(fā)送間隔，實現(xiàn)網(wǎng)絡拓撲的低開銷維護。

1 OLSR 協(xié)議的拓撲發(fā)現(xiàn)與維護機制

通過周期性地泛洪TC 消息以實現(xiàn)OLSR 協(xié)議的拓撲發(fā)現(xiàn)和維護，相比傳統(tǒng)LSR 協(xié)議，OLSR 協(xié)議提出的MPR 機制極大地減少了TC 消息的發(fā)送內(nèi)容和轉發(fā)數(shù)量。由于節(jié)點的TC 消息需要在全網(wǎng)范圍內(nèi)轉發(fā)，因此發(fā)送TC 消息造成的開銷將直接影響網(wǎng)絡性能。

1.1 TC 消息的產(chǎn)生及其交互機制

TC 消息發(fā)送前需進行MPR 集的計算，傳統(tǒng)OLSR 協(xié)議中每個節(jié)點獨立進行MPR 集的選取，選取過程應遵循以下規(guī)則：1）源節(jié)點的MPR 集應當只能從本節(jié)點的一跳對稱鄰居中選?。?）選擇出來的MPR 集能覆蓋本節(jié)點所有的兩跳鄰居，并且MPR 集中的元素個數(shù)要盡可能少。

OLSR 協(xié)議中只有當節(jié)點的MPR 選擇集不為空時才允許發(fā)送TC 消息，消息內(nèi)容為MPR 選擇集中節(jié)點的地址。整個網(wǎng)絡中所有的節(jié)點都能接收并處理該消息，但是只有MPR 節(jié)點才能轉發(fā)TC 消息。參照RFC3626［8］相關協(xié)議規(guī)范，TC 消息的收發(fā)和相關處理流程按如下步驟進行。

步驟1節(jié)點判斷自己的MPR 選擇集是否為空，當其不為空時，將MPR 選擇集中的內(nèi)容加入到TC 消息的消息體中進行廣播。

步驟2當節(jié)點收到TC 消息后，如果重復表中有一個表項的消息源地址與TC 消息的源地址相同，并且其消息序號大于等于當前TC 消息的消息序號，說明已經(jīng)處理過更新的TC 消息，則丟棄該消息不作處理，否則，執(zhí)行步驟3。

步驟3如果拓撲表中存在表項的“T_last”與TC 消息源發(fā)送者的地址相同并且對應的序號大于TC 消息中的序號，表明該消息已過期，丟棄不作處理，否則，執(zhí)行步驟4。

步驟4如果拓撲表中存在表項的“T_last”和TC 消息的源發(fā)送者地址相同，則按TC 消息中的內(nèi)容對其進行更新；否則，添加新的條目，其“T_last”為TC 消息的源地址，“T_dest”為TC 消息的內(nèi)容部分。

步驟5當TC 消息的上一跳地址在MPR 選擇集中并且消息中的“TTL”字段的值大于等于1 時，先將該字段的值減1，進而將該TC 消息進行廣播轉發(fā)。

1.2 問題描述

在OLSR 的拓撲維護過程中，節(jié)點在收到HELLO 消息后計算自己的MPR 集，當TC 消息發(fā)送定時器到期時，對自己MPR 選擇集中的地址進行廣播，被其MPR 節(jié)點進一步轉發(fā)，直至全網(wǎng)，從而實現(xiàn)了節(jié)點本地拓撲信息的全網(wǎng)通告。

1.2.1 傳統(tǒng)MPR 選擇算法

在OLSR 協(xié)議中，MPR 集是采取貪心策略進行計算的，每個節(jié)點依次將那些連接兩跳鄰居數(shù)目最多的一跳鄰居加入MPR 集，直到選出的MPR 集能夠覆蓋所有兩跳鄰居為止。廣播中繼泛洪如圖1 所示，節(jié)點S 按傳統(tǒng)MPR 選擇算法計算的MPR 集為｛b，c，d，f｝，而實際最小MPR 集為｛b，d，f｝，存在冗余。由于只有MPR 節(jié)點才能發(fā)送和轉發(fā)TC 消息，因此MPR 集中元素增加將會導致更多的節(jié)點發(fā)送TC 消息，以及TC 消息的轉發(fā)次數(shù)會增多，從而造成控制開銷增大。

圖1 廣播中繼泛洪示意圖Fig.1 Schematic diagram of broadcast relay flooding

1.2.2 TC 消息冗余發(fā)送

OLSR 協(xié)議中由于TC 消息的發(fā)送周期固定，并且每個周期發(fā)送的內(nèi)容相互獨立，因此可能造成拓撲信息冗余發(fā)送和帶寬資源浪費。拓撲變動前后對比如圖2 所示。

圖2 拓撲變動前后對比Fig.2 Comparison before and after topology change

從圖2 可以看出，帶有陰影部分的節(jié)點為該網(wǎng)絡拓撲下的MPR 節(jié)點，只有這些節(jié)點才產(chǎn)生和轉發(fā)拓撲控制消息。根據(jù)圖2 中拓撲變動前后關系計算每個節(jié)點的MPR 選擇集如表1 所示。

表1 拓撲變動前后節(jié)點的MPR 選擇集Table 1 MPR selection set of nodes before and after topology change

從圖2 和表1 可以看出，當網(wǎng)絡拓撲變化時網(wǎng)絡中MPR 集的依賴關系也會相應改變。相比網(wǎng)絡拓撲變動前，節(jié)點A 的MPR 選擇集增加了一個元素；節(jié)點D 改變了一個元素；節(jié)點B 和節(jié)點E 的MPR 選擇集保持不變。按照OLSR 原始協(xié)議的TC 發(fā)送流程，節(jié)點A 當前發(fā)送的TC 消息中將包含｛B，C，D，E，F(xiàn)，H｝的地址，其中｛C，D，E，F(xiàn)，H｝在上一周期中已經(jīng)發(fā)送過，因此重復發(fā)送將導致網(wǎng)絡帶寬浪費；節(jié)點D的MPR 選擇集變化較小，如果全部發(fā)送則會造成網(wǎng)絡控制開銷增大。

原始協(xié)議中TC 消息采用固定周期進行發(fā)送，將導致以下兩方面的問題：1）當網(wǎng)絡拓撲變動時，固定的發(fā)送間隔不能及時將拓撲變動通告全網(wǎng)，可能導致網(wǎng)絡拓撲更新不及時使丟包率增大；2）當節(jié)點周圍網(wǎng)絡拓撲較穩(wěn)定時，較短的發(fā)送周期將會導致網(wǎng)絡控制開銷和端到端時延增大。

2 LCTM-OLSR 算法

為了解決上述問題，本文提出一種低開銷的LCTM-OLSR 算法。該算法首先去除傳統(tǒng)MPR 選擇算法中存在的冗余，減少了TC 消息的產(chǎn)生數(shù)量和轉發(fā)次數(shù)；其次LCTM-OLSR 算法根據(jù)網(wǎng)絡拓撲的變動情況自適應地上下調整TC 發(fā)送間隔以實現(xiàn)網(wǎng)絡拓撲維護，并且當節(jié)點周圍拓撲變動較小時，采用發(fā)送變量信息代替全量信息以減少拓撲信息的冗余發(fā)送。

2.1 算法流程

綜上所述，本文提出一種低開銷的拓撲維護算法，該算法流程如圖3 所示。

圖3 LCTM-OLSR 算法流程Fig.3 Procedure of LCTM-OLSR algorithm

LCTM-OLSR 算法先通過最小MPR 選擇機制，將一跳鄰居按照連接度從小到大實行退出MPR 選擇，進而將關鍵的一跳鄰居節(jié)點依次加入MPR 集，去除傳統(tǒng)MPR 選擇算法中存在的冗余。在當前MPR 選擇集不為空時，節(jié)點判斷當前MPR 選擇集和上一發(fā)送周期相比是否變動，相應地發(fā)送TC_KEEP、TC_NORM、TC_DEL 消息，并動態(tài)地調整發(fā)送周期的大小，從而降低網(wǎng)絡拓撲信息的冗余發(fā)送，提高網(wǎng)絡的適應能力。

LCTM-OLSR 算法在控制開銷較少的情況下使網(wǎng)內(nèi)的每個節(jié)點掌握全網(wǎng)的拓撲信息，由于無線信道的特性，易受到干擾而丟包，可能造成部分TC 消息丟失而產(chǎn)生錯誤迭代。因此在每隔5 個TC 發(fā)送周期后，需發(fā)送一次正常的TC 消息，即TC 重置消息，進行全網(wǎng)拓撲矯正。當有新節(jié)點加入時，由于只能獲取部分網(wǎng)絡拓撲信息，當其有數(shù)據(jù)進行傳輸時可先將數(shù)據(jù)包發(fā)送至MPR 鄰居，然后由MPR 鄰居轉發(fā)至全網(wǎng)，待TC 重置消息到來后便可獲得全網(wǎng)拓撲進行正常流程通信。

2.2 算法設計

為了使全網(wǎng)節(jié)點掌握自身的拓撲信息，網(wǎng)絡中的MPR 節(jié)點會周期性地泛洪TC 消息，消息內(nèi)容由所有將自己選為MPR 一跳鄰居的地址組成并且只能由該節(jié)點選擇的MPR 節(jié)點轉發(fā)。

2.2.1 最小MPR 集選擇機制

傳統(tǒng)MPR 選擇算法采用貪心策略計算MPR集，以一跳鄰居連接的兩跳連接度作為MPR 選擇的唯一依據(jù)，沒有考慮反向兩跳鄰居和一跳鄰居間的關聯(lián)性，可能產(chǎn)生冗余的MPR 節(jié)點，影響網(wǎng)絡性能。廣播中繼泛洪拓撲扁平化如圖4 所示。

圖4 廣播中繼泛洪拓撲扁平化Fig.4 Topological flattening of broadcast relay flooding

在上述分析的基礎上，本節(jié)提出一種最小化的MPR 集選取策略，以圖4 為例最小化MPR 集的選擇步驟如下：

第一，中英兩國文化的差異。 由于地理位置、歷史等諸多方面的原因，中英兩國的文化在民族思想、宗教信仰、價值觀念、習俗等方面有著巨大差異。 基督教對英國的文化有著很大的影響，而對中國文化產(chǎn)生重大影響的宗教是佛教。 中國文化體現(xiàn)出群體性的特征，往往是不允許個人價值凌駕于群體利益之上的。 但是，英國文化體現(xiàn)出個體性的特征，即崇尚個人價值，宣揚個人主義，竭力表現(xiàn)自我和發(fā)展自我。

步驟1統(tǒng)計一跳鄰居和兩跳鄰居的連接關系，可得f=｛H｝，a=｛A，B｝，b=｛A，B，C，D｝，c=｛B，C，D，E，F(xiàn)｝，d=｛E，F(xiàn)，G｝，e=｛G｝，g=｛｝。根據(jù)連接兩跳鄰居的個數(shù)從小到大將一跳鄰居進行排序并刪除連接度為0 的節(jié)點，可得排序后的一跳鄰居為N1(i)=｛e，f，a，d，b，c｝。

步驟2對兩跳鄰居N2(i)=｛A，B，C，D，E，F(xiàn)，G，H｝分別計算其連接一跳鄰居的數(shù)目，得關聯(lián)度Link=｛2，3，2，2，2，2，2，1｝。

步驟3如果N2(i)為空，則執(zhí)行步驟5；否則將N1(i)中的節(jié)點按從左到右的順序試著退出MPR 的選取，判斷將該節(jié)點連接N2(i)中節(jié)點對應的Link 數(shù)組中的計數(shù)值減1 后，對應元素減完后的值是否都大于等于1。如果是，說明該節(jié)點為冗余節(jié)點，將其從N1(i)中剔除，Link 數(shù)組中對應的元素減1，并繼續(xù)執(zhí)行步驟3；否則執(zhí)行步驟4。

步驟4將該節(jié)點加入MPR 集并將其從N1(i)中剔除，將該節(jié)點連接的兩跳鄰居從N2(i)中剔除，繼續(xù)執(zhí)行步驟3。

步驟5此時N2(i)為空，最小MPR 集計算結束。

步驟3 將一跳鄰居按連接度從小到大的順序嘗試退出MPR 集選取，針對圖4 中的拓撲，一跳鄰居g、e、a、c 依次退出MPR 的選取，節(jié)點f、d、b 依次被選為MPR節(jié)點，此時選出的MPR 集｛b，d，f｝是最小MPR 集。

2.2.2 TC 消息自適應發(fā)送機制

TC 消息自適應發(fā)送機制分為發(fā)送內(nèi)容自適應發(fā)送機制和發(fā)送周期自適應發(fā)送機制。

在自組織網(wǎng)絡中，當前TC 發(fā)送周期的MPR 選擇集由在上一發(fā)送周期的MPR 選擇集的基礎上減去刪減量再加上新增量組成，如式（1）所示：

其中：ξlast為上一周期MPR 選擇集中的內(nèi)容；ξkeep、ξadd和ξdel分別為當前MPR 選擇集相較于上一周期的不變、增加和刪減部分，ξkeep=ξcur∩ξlast。由式（1）可知，當網(wǎng)絡拓撲變動不劇烈時，當前TC 消息內(nèi)容和上次發(fā)送的內(nèi)容會有較大的冗余，如果重復發(fā)送會造成較多的網(wǎng)絡帶寬浪費。針對此問題，LCTM-OLSR 算法提出了TC 內(nèi)容自適應發(fā)送機制，改進后TC 消息內(nèi)容如式（2）所示：

當前周期TC 消息內(nèi)容可根據(jù)網(wǎng)絡拓撲的變動情況而動態(tài)調整，按MPR 選擇集的變動情況將TC消息分為3 種類型，具體發(fā)送步驟如以下2 種情況：

（1）當節(jié)點周圍拓撲發(fā)生變動時，如果ξdel<ξkeep，則由刪減量和新增量組成TC_DEL 消息進行發(fā)送；反之，則由不變量和新增量組成TC_NORM 消息進行發(fā)送。

（2）當節(jié)點周圍拓撲保持不變時，發(fā)送消息體為空的拓撲保持消息TC_KEEP，節(jié)點接收該消息后更新拓撲表項的生存時間。

為適應改進機制變動，TC 消息包格式將Reserved 字段劃分為TC_Type 和Del_len 兩部分，分別表示當前TC 消息的類型和消息體中前Del Len 個地址為刪減部分，其中Del_len 字段的值在消息類型為TC_KEEP 和TC_NORM 時為0，改進后的TC 消息格式如圖5 所示。

圖5 改進后的TC 消息包格式Fig.5 Improved TC message packet format

對比圖2（a）和圖2（b）的拓撲變動，在變動后原始協(xié)議和改進協(xié)議發(fā)送的TC 消息內(nèi)容如表2所示。

表2 拓撲變動后原始和改進協(xié)議TC 消息內(nèi)容Table 2 Original and improved protocol TC messages after topology change

從表2 可以看出，拓撲變動后只有A、B、D、E 4 個節(jié)點的MPR 選擇集不為空，按原始協(xié)議它們需要將自己MPR 選擇集中的地址裝入TC 消息中發(fā)送出去。按照改進機制，節(jié)點D 的MPR 選擇集的減少量為｛E｝，不變量為｛A，K，M｝，增加量為｛C｝，減少量小于不變量，故D 節(jié)點當前發(fā)送內(nèi)容為｛E，C｝；同理，節(jié)點A 只需發(fā)送增加量｛B｝，節(jié)點B 和E 的MPR選擇集沒有發(fā)生變化，只需要發(fā)送消息體為空的TC_KEEP 消息即可，有效地降低了拓撲維護時的控制開銷。

2）TC 消息周期自適應發(fā)送機制

在RFC3626［8］中，OLSR 協(xié) 議TC 消息的 發(fā)送周期為恒定值Tmid=5 s，當網(wǎng)絡拓撲變動較頻繁時，不能及時更新網(wǎng)絡拓撲信息而導致丟包率增大；當網(wǎng)絡拓撲較穩(wěn)定時，較短的發(fā)送周期將導致網(wǎng)絡控制開銷增大，因此固定TC 發(fā)送周期不能很好地適應自組織網(wǎng)絡中網(wǎng)絡拓撲的變動。

基于此，LCTM-OLSR 算法將當前TC 發(fā)送間隔（TC Emission Interval，TCEI）以原始發(fā)送周期5 s 為中點劃分為5 個層級，從小到大依次為Tmin、Tless、Tmid、Tlong、Tmax，并且網(wǎng)絡拓撲變動越頻繁，TC值設置得越小，由歷史上的發(fā)送周期大小和鏈路信息保持狀態(tài)綜合決定當前TC 消息的發(fā)送頻率。其中，觸發(fā)TC 消息發(fā)送周期變動的條件為：

（1）當節(jié)點MPR 選擇集變動，即MPR 選擇集增加或減少元素時，如果上一次的發(fā)送周期表明歷史上至少一個周期內(nèi)節(jié)點周圍網(wǎng)絡拓撲未變動，此時網(wǎng)絡正由較穩(wěn)定轉變?yōu)椴环€(wěn)定狀態(tài)，下一次的發(fā)送周期應重置為；否則在的基礎上下降一個層級。

（2）當節(jié)點MPR 選擇集在一個發(fā)送周期內(nèi)維持不變時，如果此時，表明歷史上節(jié)點周圍拓撲較不穩(wěn)定，并且此時網(wǎng)絡正由不穩(wěn)定向穩(wěn)定狀態(tài)轉變，則下一次發(fā)送周期應該重置為Tmid；否則在的基礎上上調一個層級。

在拓撲關系變動時，為了使網(wǎng)絡中其他節(jié)點感知到拓撲改變，MPR 節(jié)點應盡快將改變后的拓撲信息發(fā)送出去。TC 消息快速發(fā)送時間分析如圖6所示。

圖6 TC 消息快速發(fā)送時間分析Fig.6 Analysis on the fast sending time of TC messages

從圖6 可以看出，t1為上次發(fā)送TC 消息的時間，t2為當前時間，t3為當前時間加上變動后TC的時間點，t4為預計下次發(fā)送時間。假設節(jié)點在t2時刻MPR選擇集發(fā)生改變，按LCTM-OLSR 算法將TC 下一周期發(fā)送時長下調一級，如果t3

2.3 LCTM-OLSR 算法的性能分析

在自組織網(wǎng)絡中由于網(wǎng)絡拓撲的動態(tài)變化，影響網(wǎng)絡性能指標的因素主要有網(wǎng)絡中節(jié)點的總數(shù)、節(jié)點的發(fā)包速率、包的大小、節(jié)點的移動速度等［20］。在OLSR 協(xié)議中，路由信息主要通過節(jié)點周期性地交互HELLO 和TC 消息來進行更新維護。網(wǎng)絡相關運行參數(shù)的定義如下：

N：整個自組織網(wǎng)絡中節(jié)點的總數(shù)；

NMS：網(wǎng)絡中選取MPR 節(jié)點的總數(shù)，其值與網(wǎng)絡規(guī)模N 和MPR 選擇算法相關；

Nm：網(wǎng)絡中每個節(jié)點平均選取MPR 節(jié)點的個數(shù)；

Shello：發(fā)送的HELLO 消息的單條平均長度；

STC：發(fā)送的TC 消息的單條平均長度；

Thello：HELLO 消息的發(fā)送周期；

TTC：TC 消息的發(fā)送周期。

因此，自組織網(wǎng)絡運行時網(wǎng)絡中某個節(jié)點i在單位時間內(nèi)總共產(chǎn)生的HELLO 消息長度如式（3）所示：

同理，MPR 節(jié)點j單位時間內(nèi)可產(chǎn)生TC 消息的長度如式（4）所示：

考慮到多點中繼，同一條TC 消息需要向其Nm個MPR 鄰居節(jié)點進行轉發(fā)，因此在單位時間內(nèi)MPR 節(jié)點j需轉發(fā)總的TC 消息長度為：

只有MPR 節(jié)點才產(chǎn)生和轉發(fā)TC 消息，那么單位時間內(nèi)整個自組織網(wǎng)絡所產(chǎn)生的總路由開銷為：

由式（6）可知，降低HELLO 和TC 消息的長度或減少網(wǎng)絡中MPR 節(jié)點個數(shù)均可以降低OLSR 協(xié)議的控制開銷。本文提出LCTM-OLSR 算法采用TC 消息自適應發(fā)送的方法降低了STC，增大了TTC，并且最小MPR 集選擇機制有效地減少了網(wǎng)絡中MPR 節(jié)點的個數(shù)，有效地降低了OLSR 協(xié)議拓撲維護的控制開銷，提升了網(wǎng)絡的吞吐量。

3 實驗與結果分析

選取標準OLSR協(xié)議，參考文獻［18］中的HTR-OLSR協(xié)議與本文的LCTM-OLSR 協(xié)議作為分析比較對象，通過仿真實驗對比分析它們之間的發(fā)包成功率、端到端時延、吞吐量。

3.1 仿真參數(shù)設置

本文使用Windows XP 平臺上OPENT Modeler 14.5 仿真軟件，對OLSR、HTR-OLSR 和LCTM-OLSR協(xié)議進行仿真對比，設置5 個仿真場景。假設實驗中每個節(jié)點的發(fā)射和接收功率都相同，節(jié)點的最大通信距離為200 m，TC 消息的發(fā)送周期變動范圍｛Tmin，Tless，Tmid，Tlong，Tmax｝在本次仿真實驗中分別設置為｛3 s，4 s，5 s，6 s，7 s｝。仿真具體參數(shù)如表3 所示，本實驗每個場景實驗做5 次，取實驗結果的平均值，主要考察不同移動速度對網(wǎng)絡性能的影響。

表3 仿真參數(shù)設置Table 3 Simulation parameters setting

3.2 仿真結果分析

3.2.1 吞吐量

OLSR、HTR-OLSR 和LCTM-OLSR 算法的吞吐量對比如圖7 所示。LCTM-OLSR 算法的吞吐量比文獻［18］中的HTR-OLSR 算法平均提高了7.84%，比標準OLSR 平均提高了10.14%。因最小MPR 選擇算法減少了MPR 節(jié)點個數(shù)，從而減少了TC 消息的發(fā)送和轉發(fā)次數(shù)，同時TC 自適應發(fā)送機制通過對發(fā)送內(nèi)容進行優(yōu)化，減少了網(wǎng)絡控制開銷，提高了吞吐量。當節(jié)點速度加快時，網(wǎng)絡拓撲變動加快，數(shù)據(jù)包丟失概率增大，吞吐量明顯下降。此時LCTMOLSR 算法會自適應地降低TC 消息發(fā)送間隔，及時更新變化后的網(wǎng)絡拓撲，進而提高數(shù)據(jù)包接收的成功率；并且該算法TC 數(shù)據(jù)包比其他兩種算法小，有效降低了冗余拓撲信息的傳輸，所以在節(jié)點移動速度加快時，該算法相較于其他兩種算法能夠一直維持較高的網(wǎng)絡吞吐量。

圖7 OLSR、HTR-OLSR 和LCTM-OLSR 算法吞吐量對比Fig.7 Throughput comparison of OLSR，HTR-OLSR and LCTM-OLSR algorithms

3.2.2 端到端平均時延

OLSR、HTR-OLSR 和LCTM-OLSR 算法的端到端時延對比如圖8 所示。改進后的LCTM-OLSR 算法具有更低的端到端傳輸時延，相比HTR-OLSR 算法平均降低了10.24%，比標準OLSR 平均降低了19.87%。當節(jié)點移動速度加快時，網(wǎng)絡拓撲變動更頻繁，此時LCTM-OLSR 算法會自適應地加快TC 消息的發(fā)送頻率，使網(wǎng)絡中的節(jié)點能更及時地獲取到其他節(jié)點最新的拓撲信息，從而計算出當前時間到達目的節(jié)點的最佳路由，因而LCTM-OLSR 算法仍然能夠維持較低的端到端時延。HTR-OLSR 算法雖然通過減少HELLO 和TC 消息的發(fā)送間隔能在一定程度上降低端到端傳輸時延，由于該算法在MPR 選取時考慮節(jié)點的能量因素，使節(jié)點計算出的路徑不是最短，導致時延增大。

圖8 OLSR、HTR-OLSR和LCTM-OLSR算法端到端時延對比Fig.8 End-to-end delay comparison of OLSR，HTR-OLSR and LCTM-OLSR algorithms

3.2.3 發(fā)包成功率

OLSR、HTR-OLSR 和LCTM-OLSR 算法的發(fā)包成功率對比如圖9 所示。LCTM-OLSR 算法的發(fā)包成功率高于其他兩種算法，相比文獻［18］中的HTR-OLSR 算法平均提高了3.37%，比標準OLSR平均提高了8.63%，并且當節(jié)點移動速度變快時三種算法的發(fā)包成功率均明顯下降。當節(jié)點移動速度加快時，網(wǎng)絡拓撲變化加快，節(jié)點的拓撲信息和路由信息的有效時間縮短，從而導致數(shù)據(jù)包丟包率增加。LCTM-OLSR 算法根據(jù)節(jié)點周圍網(wǎng)絡拓撲的歷史變動信息，自適應地調節(jié)TC 消息的發(fā)送周期，在網(wǎng)絡拓撲變動頻繁的情況下通過加快TC 消息的發(fā)送，及時更新節(jié)點路由表中因為拓撲變動而失效的路由表項，從而有效提升了數(shù)據(jù)包的發(fā)包成功率。

圖9 OLSR、HTR-OLSR 和LCTM-OLSR 算法發(fā)包成功率對比Fig.9 Contract success rate comparison of OLSR，HTROLSR and LCTM-OLSR algorithms

4 結束語

本文通過對OSLR 協(xié)議中MPR 集的選取過程進行優(yōu)化，提出一種低開銷拓撲維護算法。該算法在穩(wěn)定量與刪減量中選擇較小量與新增量組成TC消息進行發(fā)送，并根據(jù)拓撲變動消息能自適應地調整TC 消息發(fā)送。實驗結果表明，相比OLSR 和HTR-OLSR 算法，LCTM-OLSR 算法減少了網(wǎng)絡控制開銷同時提高了網(wǎng)絡吞吐量和網(wǎng)絡應對拓撲變化的適應能力。下一步將對鄰居發(fā)現(xiàn)機制進行研究以減少網(wǎng)絡中因鄰居發(fā)現(xiàn)而產(chǎn)生的冗余，提高網(wǎng)絡性能。