基于改進BERS算法的移動自組織網絡能耗及時延優化

宋國平

（吉林廣播電視大學遠程教育技術中心，吉林 長春 130022）

0 引言

MANET依靠移動節點的合作來動態建立通訊路由［1－3］，因為節點一般是由電池供電的，能源和時效對 MANET 尤為重要［4－5］.

為了節省MANET的能量消耗及降低時延，人們提出了許多路由方案，典型的分層架構是通過聚類結構實現的，例如，文獻［6］提出了一種高度聚類啟發式算法，基于節點到其他節點的距離計算節點度，該方法存在一個很大的缺點，它沒有在任何聚類中限制節點數目的上限，嚴重影響了聚類的吞吐量和穩定性.文獻［7］提出一個最低ID聚類啟發式算法，它為每個移動節點安排一個唯一ID，選擇最低ID的節點作為聚類頭節點，該方法的吞吐量比高度聚類方法好，然而，有較小ID的節點往往反復選為聚類頭節點，這可能會很快耗盡電池電量.文獻［8］提出了分布式聚類算法和分布式移動自適應聚類算法，也稱為節點加權啟發式算法，啟發式評估每個節點作為聚類頭節點的適宜性，并安排對應的節點權重，然而，一個節點必須等到它所有鄰居的應答才能確定是聚類頭節點還是聚類成員.文獻［9］中研究了負載均衡聚類，它相信一個聚類能處理的移動節點數目有個最優值，當聚類太大或太小時將相鄰聚類合并在一起或者分離某個聚類.文獻［10］提出一種加權聚類啟發式算法，合并了聚類的各種指標，如連接到聚類頭節點的節點數目、發送功率、移動性和節點電源能量，遺傳算法和模擬退火算法已經改進了這個方法.阻塞擴展環搜索（Blocking Expanding Ring Search，BERS）和加強阻塞擴展環搜索（BERS＊）是近期為MANET 開發出的2個路由發現協議［11－12］.相比ERS和BERS，BERS＊在能源時效方面能獲得了更好的整體性能.BERS和BERS＊均使用一個追包，在BERS中為STOP，在BERS＊中為END，用于發現路由節點后終止泛洪［13］.為了討論方便，后續稱BERS中的STOP或BERS＊中的END為STOP／END指令.STOP／END指令只能由BERS和BERS＊中的源節點發出，源節點直到第一個路由應答（RREP）到達后才能發出STOP／END指令，即沒有因等待RREP所引起的延遲就不能發出STOP／END指令［14］.

基于上述分析，為了更好地降低時延和節省能耗，本文提出了基于路由節點泛洪終止的阻塞擴大環搜索方案，一旦發現路由節點就可以發送STOP／END指令，而不是等待源節點發送STOP／END指令，路由節點也可以參與發送STOP／END指令終止泛洪，仿真實驗驗證了所提方案的有效性及可靠性.

1 相關工作

1.1 擴展環搜索

ERS是一個尋找源節點和路由節點之間路由的有效方法，路由節點也稱作目的端或能提供到目的端路由信息的節點.作為一個受約束的泛洪技術，ERS頻繁地用在反應式路由協議中，通常從一個預定義的小搜索區域開始，如果沒有發現路由節點ERS在一個每次擴大的搜索區域內從源節點執行新搜索，這個增量式搜索過程一直持續到發現路由節點或達到最大搜索區域.ERS中的泛洪搜索涉及在連續和中繼方式下經由中間節點的重播，就像一個逐漸擴展的搜索區域，環到環、從小環到大環.

ERS中的源節點初始化泛洪并控制每個擴展泛洪的搜索區域及最大搜索區域，有2個控制信號用于ERS中有效控制泛洪，RREQ和RREP.為了最小化泛洪，ERS采用生命周期（Time to Live，TTL）機制，TTL序列決定泛洪搜索的順序，可能會在一個特定的值上加一個增量、固定值1或者2、或隨機值.圖1顯示了泛洪區域集如何受預定義TTL序列值1，2，3，…，n控制.

圖1 擴展環搜索

基于TTL的ERS能源效率低下（如圖1所示），如果源節點收不到RREP，源節點將會以一個增加的TTL值重播RREQ，每次源節點進行新RREQ的重播都會引入能源浪費.先前的覆蓋搜索區域重疊會造成冗余，發現路由節點之前或搜索完整個網絡會多次出現這種情況.

1.2 阻塞擴展環搜索（BERS）

BERS可認為是能效ERS，BERS采取了一個策略，即源節點經過重新泛洪的中間節點右側.BERS的源節點僅發送一次RREQ，中間節點當做一個代理，代表源節點進行重播.為了滿足這個策略，BERS要實施一個擴展的2 H個單位等待時間，其中H是跳數.然而源節點仍有義務終止路由發現過程，收到RREP時源節點發送STOP指令去終止泛洪，泛洪持續直到追包，也就是STOP指令，在最后一個泛洪環Hr到達所有結點，在這個環中發現路由節點.

圖2顯示了BERS如何在從一個環到下一個環傳播搜索，在BERS中，源節點首先發送RREQ，等待RREP，如果在第一個環中未發現路由節點，在第一個環中的節點以一個增加了的跳數重播RREQ，這個過程一直持續到源節點接收到RREP，然后源節點廣播STOP指令去終止搜索.STOP指令只能由源節點發送，泛洪中涉及的結點將接收STOP指令，RREP可以由任意路由節點發送到源節點.為了在發現路由節點后能有效地終止下一次泛洪，BERS在每一輪泛洪過程中均要求一個擴展的2 H個單位等待時間.

圖2 阻塞擴展環搜索

1.3 加強阻塞擴展環搜索（BERS＊）

BERS＊是基于BERS的，旨在減少BERS的延遲，獲得能源時效方面最佳的整體性能.

BERS＊的工作方式與BERS相似，除了它在每一輪泛洪過程中減少了一半的等待時間.BERS＊中的中間節點在源節點發送了RREQ后接管后續環搜索上的重播任務，如果這些中間節點不是路由節點，在重播RREQ之前需H個單位等待時間.

相對于BERS中的2 H單位等待時間，BERS＊的整體路由發現過程速度加快近2倍，改進了能源時效方面路由發現的整體性能.如果在Hr環為節點取2 Hr單位時間來接收END泛洪信號，BERS＊中泛洪可能會在Hr＋1環終止，比路由節點發現環多出一個環.

圖3所示為BERS＊的工作流程圖，從圖3中可以看出，在等待和傳播RREP和END指令之間由于節點動作同時發生，所以僅需要一個額外環.首先，在并發行動開始之前RREP從路由節點R到源節點S（箭頭線）傳輸花費Hr單位時間；其次，在下一個單位等待時間內，END指令廣播到環1，而節點a和b繼續泛洪從Hr到Hr＋1（紅色箭頭線）；此外，在Hr＋1單位等待期間END包花費下一個Hr單位時間追上節點c（在環1從u開始的虛線箭頭線）.

圖3 加強阻塞擴展環搜索

2 優化方案提出

為了減少了延遲而不增加能耗，提出了加強的BERS（tBERS）和加強的BERS＊（tBRES＊），采用追包的名字，代表tBERS的STOP和tBERS＊的END與tBERS／tBERS＊的STOP／END.tBRES的工作方式與BRES相同，tBRES＊與BRES的工作方式相同，除了tBRES和tBRES＊允許路由節點發送STOP／END指令.通過發送終止指令的路由節點右側，相比于BERS和BERS＊，tBERS和tBERS＊能分別減少BERS和BERS＊的延遲，減少的延遲量等于Hr，也就是RREP到達源節點的傳輸時間.

在BERS和BERS＊中僅由源節點發送STOP／END指令終止泛洪，在tBERS和tBERS＊中，一旦接收到RREP，正如BERS和BERS＊，源節點也發送STOP／END指令，然而，這樣的目的是終止先前由路由節點發送的STOP／END未覆蓋的剩余泛洪，這部分泛洪由環Hr上的那些節點引起，但是由于他們的地理位置不能到達，在RREP單播傳送時未從路由節點接收到STOP／END.此外，在tBERS和tBERS＊中，源節點接收到RREP之后不久就已經準備好發送數據包了.

tBERS和tBERS＊都吸取了并發活動的優點，第一類并發活動發生在RREP單播傳送和從路由節點多播傳送STOP／END之間，盡管由路由節點發送的STOP／END可能追不上環Hr中的所有節點去終止泛洪，但tBERS和tBERS＊中的這個方法旨在停止環Hr中進一步泛洪的一些節點，更早一些執行這個動作，否則會在BERS和BERS＊中執行.第二類并發活動發生在源節點發送數據包和STOP／END指令之間，這允許數據包比在BERS和BERS＊中更早傳輸.

可以證明tBERS的能耗級別與BERS相同，然而，tBERS＊能節省能源.在BERS＊中，Hr＋1環終止泛洪，超過發現路由節點一個環，相反，tBERS＊中僅有一部分泛洪在這個額外環上終止，而剩余的泛洪較早的在Hr環上終止了，也就是發現路由節點的環.這是因為在環Hr中的一些節點會在它們的Hr單位等待時間內接收到END指令.

圖4顯示了tBERS＊的一個實例，其中節點d停止泛洪早，盡管它比路由節點R多一跳.這里節點d在環Hr上，但是與路由節點R超過了一跳距離，然而，節點d將從路由節點R接收一個END信號途經節點b和c.相反，如果是在BERS＊中，節點d將在Hr單位等待時間之后多廣播一個環，泛洪將不會終止直到環Hr＋1.

圖4 tBERS＊示例

節點均勻分布的情況下，在環Hr中約1／3的節點可能在它們的等待時間內接收END消息，如圖5所示，其中淺色標記的節點涉及RREPs到達源節點S之前泛洪終止.

上述的均勻分布是tBERS＊的最佳情況，在最差情況下，可能因其地理位置而環Hr中沒有非路由節點從路由節點接收到END指令，在這種情況下，tBERS＊的工作方式與BERS＊完全相同，即在第2個Hr周期內接收源節點的END指令.

圖5 tBERS＊均勻分布節點

在tBERS或tBERS＊中的路由節點有義務發送RREP和STOP／END指令，有2種方式可以實現同時發送RREP和STOP／END指令，其一是合并RREP和STOP／END到一起，其二是先發送RREP指令，接下來再發送STOP／END指令.注意，RREP以單播方式發送，而STOP／END是廣播.作為一個示例，為了在算法中強調本文研究的思想，本文tBERS＊取第2種方法.

2.1 算法

下面僅給出tBERS＊的4個算法，tBERS的算法是類似的.注意算法中使用END指令終止泛洪，算法1是針對源節點，算法2，3和4是針對中間節點和路由節點.

算法1覆蓋了路由發現過程中源節點的動作，這包括用第一次發送RREQ（行1）來初始化路由發現過程、處理RREPs中的路由信息（行4，5）.為了避免END指令和數據包之間的沖突，本文為數據包引入一個單位時間的滯后，即調用procedure＿data＿packets（行6）之前等待一個單位時間.

類似的，算法2總結了中間節點的行動，根據接收的3個消息（RREQ，RREP和END）.

算法3和4是2個描述中間節點分別接收到RREQ和END時動作的程序，如果是路由節點，它將初始化并廣播END指令（算法3行8）.

算法3中，當識別出路由節點，將以當前跳數發送RREP（即 Hr）到源節點（行5～8），其他中間節點需要等待H 個單位時間（行10），如果沒有收到END指令則開啟泛洪（行18～19），在等待期間，中間節點需要發送一個END（行12～13，在算法4中調用procedure＿end）或 RREP（行15），因為可能源節點有第2個RREP作為備份.

2.2 能耗和時延計算

本章比較了ERS，BERS，tBERS，BERS＊和tBERS＊的能耗和延遲，結果如表1所示，各個符號說明如表2所示，這里已經消除了量化能耗和發現延遲的數學細節，可以從文獻［11－12］中找到為ERS，BERS和BERS＊進行的詳細計算，而tBERS和tBERS＊的能耗和延遲計算分別遵循BERS和BERS＊.

表1 各算法的能耗和時延計算

從表1可以看出，tBERS的延遲是Hr＋，tBERS＊的延遲是1＋1.5 Hr＋0.5 H2r，而BERS和tBERS的能耗是相同的，tBRES＊的能耗量低于BERS＊，依賴于節點分布.

表2 術語和符號說明

3 仿真

本文基于上述分析結果執行了一系列的仿真，在IDL6.0系統（研究系統、Boulder、CO、USA）上實現，主要目標是調查新策略應用到BERS和BERS＊的路由發現協議產生的改進，為了得到新方案的性能特征，在如下均勻節點分布下對ERS，BERS，tBERS，BERS＊和tBERS＊進行了一系列的實驗.假設共有1000個節點均勻的置于覆蓋Hr為10區域的地理區域內，在上述假設的節點分布下，在時效、能效和能源時效方面比較這些協議性能之間的差異.

3.1 時延比較

時效的比較結果見圖6.圖6a表明了5個方案對Hr的時間延遲，5個方案的延遲隨著Hr的增加而增加，然而，tBRES和tBRES＊的延遲比BERS和BERS＊中對應的值小，tBERS＊的時間延遲最小，這表明tBERS＊是5個方案中時間效率最高的方案.

圖6b強調了當Hr＝10時5個方案的延遲，從圖6b中可以看到，tBERS優于BERS，tBERS＊優于BERS＊，時間效率最高的方案是tBERS＊，然后依次是BERS＊，tBERS和ERS，最后是BERS.當Hr為10時，tBERS＊比BERS＊的時間效率提高約12%.

類似的，當Hr為10時，tBERS比BERS的延遲減少約7.5%.

圖6 5個方案的時延比較

3.2 能耗比較

能耗比較的結果見圖7.

圖7 5個方案的能耗比較

圖7a是5個方案對Hr的能耗圖，能耗隨著Hr的增加而增加，BERS和tBERS產生相同的能耗，這2個方案是能源效率最高的方案，tBERS＊的能耗級別低于BERS＊，相比于BERS＊，當Hr為10時，tBERS＊可節能約6%.

圖7b強調了Hr為10時5個方案的能耗，表明BERS和tBERS是能源效率最高的方案，相比于BERS＊，tBERS＊消耗的能源略低.

3.3 成本比較

為了比較各算法的整體性能，本文使用文獻［15］提出的產品模型，將全部成本定義為產品的能耗量乘以延遲量，即C＝E＊T，各算法的全部成本比較結果如圖8所示，圖8a顯示了5種方案中每個方案對Hr的能源時效.

圖8 5種方案的能源時效

從圖8a可以看出，tBERS＊是5個方案中能源時效最高的方案，其次是BERS＊.這意味著本文提出的新策略tBERS和tBERS＊分別改進了現有協議BERS和BERS＊，tBERS的整體成本低于BERS對應的成本.

圖8b強調了Hr為10時的成本比較，可以看出，tBERS＊比BERS＊的能源時效提高了近19%.

4 結束語

本文提出了一種基于路由節點泛洪終止的擴展環形搜索改進算法，最初旨在進一步減少2個現存能源或能源時效協議BERS和BERS＊的延遲，對tBERS和tBERS＊的研究結果表明，tBERS和tBERS＊是時間和能源時效更有效的2個路由協議.首先，在tBERS和tBERS＊中通過轉換終止從源節點到路由節點的泛洪義務，分別得到了比BERS更高的時效，比BERS＊更高的時間效率和能源效率，這表明在集體環境中重新分布工作負載可能會有潛在的收益.其次，本文研究中的并發對提高時間效率是有用的，而延遲和能耗有權衡的本質，所以并發既能改善時間效率，也能改善能源效率.此外，既考慮時間效率也考慮能源消耗時效是調查整體性能的一個有用度量，單獨在時間效率或者能源效率上的結果可能是片面的、不完整的，有時還會產生誤導，同時考慮時間和能耗是有益的.

［1］夏輝，賈智平，張志勇.移動Ad Hoc網絡中基于鏈路穩定性預測的組播路由協議［J］.計算機學報，2013，36（5）：926－936.

［2］葛永明，朱藝華，龍勝春，等.IEEE802.11移動自組織網絡節點競爭窗口長度的概率分布［J］.電子學報，2010，38（8）：1841－1844.

［3］吳大鵬，武穆清，甄巖.移動自組織網絡可用帶寬估計方法研究進展［J］.通信學報，2010，31（4）：103－115.

［4］張鵬，崔勇.移動自組織網絡路由選擇算法研究進展［J］.計算機科學，2010，37（1）：10－21.

［5］牛曉光，崔莉，黃長城.移動自組織網絡中基于優化分簇的混合路由協議［J］.通信學報，2010，31（10）：58－67.

［6］王安保，胡小明.基于GPS的啟發式Ad hoc路由算法研究［J］.計算機應用研究，2010，27（12）：4708－4710.

［7］BAKER D，EPHREMIDES A.The architectural organization of a mobile radio network via a distributed algorithm ［J］.Communications，IEEE Transactions on，1981，29（11）：1694－1701.

［8］王博，黃傳河，楊文忠.TRQ：Ad hoc網絡中基于QOS的可信路由算法［J］.小型微型計算機系統，2011，32（7）：1249－1254.

［9］甄巖，武穆清，吳大鵬，等.MANET多路徑負載均衡方法［J］.北京郵電大學學報，2010，33（2）：64－68.

［10］霍金海，王鉞，徐贊新，等.基于負載和優先級的MANET優化策略［J］.清華大學學報：自然科學版，2012，52（9）：1270－1274.

［11］PHAM D N，NGUYEN N T，DO X B，et al.An expending ring search algorithm for mobile adhoc networks ［C］／／Advanced Technologies for Communications（ATC），Canadian：IEEE，2010：39－44.

［12］PU I M，SHEN Y.Enhanced blocking expanding ring search in mobile ad hoc networks ［C］／／New Technologies，Mobility and Security （NTMS），Candian：IEEE，2009：1－5.

［13］王新穎，吳釗.基于AODV優化的移動自組網路由協議［J］.計算機工程，2009，35（7）：113－115.

［14］JAVAID N，BIBI A，DRIDI K，et al.Modeling and evaluating enhancements in expanding ring search algorithm for wireless reactive protocols［C］／／Electrical＆ Computer Engineering （CCECE），Canadian：IEEE，2012：1－4.

［15］PU I，SHEN Y，KIM J.Measuring energy－time efficiency of protocol performance in mobile ad hoc networks［M］／／Ad－hoc，Mobile and Wireless Networks Berlin：Springer，2008：475－486.