1、一種最小化無線自組網干擾的拓撲控制算法李曉鴻1，張大方2，蔡小莉1，王 東1(1. 湖南大學計算機與通信學院，湖南 長沙 410082；2. 湖南大學軟件學院，湖南 長沙 410082 摘 要:針對無線自組網中，如何準確度量干擾并構建干擾最小化的網絡結構的問題。根據無線通信的特點和網絡協議的機制，設計了一種基于協議的網絡干擾模型度量方法，并提出了一種啟發式的干擾最小化拓撲控制算法，該分布式算法能保證網絡連通，并使整個網絡中節點間的路徑干擾最小化。仿真結果驗證了新算法降低了網絡沖突，更好地改善了網絡性能。關鍵詞: 自組網; 拓撲控制; 干擾; 吞吐量中圖法分類號: TP393 文獻標識碼: AA

2、n Interference-avoidance Topology Control Algorithm inAd hoc NetworksLi Xiao-hong1, ZHANG Da-fang2, Cai Xiao-li1, Wang Dong1(1. School of Computer and Communication, Hunan University, Hunan Changsha 410082, China(2. School of Software, Hunan University, Hunan Changsha 410082, ChinaAbstract: In order

3、 to concretely measure and explicitly reduce the interference of the entire network in Ad hoc networks, a new protocol interference model is presented as a measure to describe the interference of the entire network in this paper. Furthermore we propose a distributed interference-avoidance topology c

4、ontrol approximation algorithm, referred to as the ISPT. The algorithm minimizes the interference in the network according to our metrics while preserving the connectivity of the resulting topology. The simulation results show that ISPT decreases interference and improves network capacity in terms o

5、f throughput.Key words: Ad hoc networks; topology control; interference; throughput1引言自組網是一種無中心、自組織的多跳無線網絡。由于其具有抗毀性、自組織性與機動性等特點，將在無線通信領域發揮越來越重要的作用。為保證無線自組網能即時、通暢和高效通信，提高自組網的傳輸能力和減少節點的能耗是自組網面臨的關鍵問題12。拓撲控制是提高網絡吞吐率和延長網絡生命周期的一種重要途徑。該技術通過調整節點的發送功率和建立合適的相鄰關系，構建全局優化網絡拓撲。其主要目標是降低節點能耗和減少通信干擾，為MAC 協議和路由協議的順利執

6、行提供基礎。近年來國內外一些學者已經初步展開了對構建自組網拓撲的理論研究和應用探討34。早期的經典拓撲控制算法主要通過控制節點發送功率或盡量稀疏化網絡拓撲圖的思想，達到降低節點信道之間干擾的目的。近階段有一些研究者，認為片面減少邊的數量、長度及鄰節點度不一定就能保證節點之間的干擾現象也降低4，并就干擾模型的定義和度量方法進行了研究5，其中定義的干擾模型有基于發送節點的干擾模型6，基于接收節點的干擾模型78和基于鏈路的干擾模型91011；而對于干擾的度量，則采用了基于網絡拓撲的點覆蓋或邊覆 基金項目：國家973重點基礎研究發展計劃(No.2007CB310702；國家自然科學基金(No.6067

7、3155李曉鴻 男, 1973年出生，湖南長沙人, 講師, 湖南大學計算機與通信學院博士研究生, 主要研究方向為可信系統與網絡、無線網絡和移動計算. Email: lixhong蓋統計方法。但是，這些定義僅僅以節點位置和覆蓋范圍度量網絡中的局部（一跳范圍）干擾，沒有考慮自組網中節點間經過路徑（即多跳）傳輸的特性對度量干擾的影響。文獻12則認為必須從網絡協議的角度出發，結合自組網數據通信機制和網絡拓撲中節點覆蓋的特點，這樣才能更準確的定義網絡拓撲干擾模型。文獻5綜述了目前已有學者基于不同的干擾模型，提出的降低網絡干擾的拓撲控制近似算法。其中文獻9基于鏈路的干擾模型，首次提出LIFE 算法構建最小

8、化最大邊干擾度的拓撲結構。文獻13提出把平均最優路徑的沖突作為衡量網絡沖突性能指標，設計API 算法以構建干擾優化的拓撲結構，但是API 算法是基于GG 圖進行剪枝處理以優化干擾，并沒有從直接尋求最優干擾路徑的角度設計算法，這使得構建的拓撲有可能沒有獲得最優干擾路徑13。而文獻14則分析并證明，全局網絡節點對之間干擾最短路徑的拓撲結構的優越性，但是沒有提出有效的分布式構建方法。上述這些通過拓撲控制降低網絡干擾的研究工作，其主要貢獻在于對拓撲結構的干擾進行定性或半定量的分析描述，但在拓撲控制算法的研究中，更多地關注降低網絡的局部或某些特殊情形的干擾，很少有算法把降低整個網絡的干擾作為主要目的，也

9、沒有充分考慮拓撲結構與網絡協議的相互關系對網絡傳輸性能的影響。而且構建算法大多不實用，時間復雜度高且大多是集中式算法，或需獲得網絡全局信息，通信代價過高。這些不足使得研究者無法就它們對網絡性能的影響進行定量評估。本文首先根據無線通信的特點和網絡協議的機制研究干擾可能發生的實際情況，提出干擾模型及度量方法，在此基礎上提出一種分布式的啟發式算法ISPT(An Interference-avoidance topology control algorithm based Shortest Path Tree。并理論證明新算法在保證整個網絡連通的前提下，可以構建任意節點間的最短路徑干擾最小化的拓撲圖；

10、同時提出了一種準干擾瓶頸節點避免機制，通過減少稀疏拓撲結構中瓶頸節點的出現，避免路由造成的流間干擾概率增大對網絡傳輸性能的影響。仿真結果驗證了算法ISPT 降低了網絡沖突，更好地改善了網絡傳輸性能。2基于協議的干擾模型和干擾度量指標在無線通信中，一個正在發送射頻信號的設備會影響周圍其它設備接收信號。如果一個設備附近有其它設備正在發送信號，那么它將不能同時正確接收其它鄰近設備發射的信號。通信中的這種相互信號擾亂稱為干擾。無線自組網的無線信道是一個共享廣播信道。目前基于CSMA/CA的IEEE802.11是一種最有效的單信道接入控制協議。通過研究802.11對無線鏈路通信的控制機制，發現發送節點和

11、接收節點在一次通信中都需要相互發送和接收不同的數據幀，由此提出基于MAC 的邊干擾模型，即無線鏈路收發兩端一次完整數據傳輸時，兩個節點都不能受到干擾。并定義如下度量干擾的公式。定義1（邊干擾）給定一個網絡拓撲圖G =(V , E ，若邊< u, v >E ，定義uv 邊的干擾為：IL(=covering( covered( covering( covered( uv u u v v （1）其中，covering(u 為節點u 的發射功率為p (u 時覆蓋的鄰近節點集合，covered(u 為節點u 被鄰近節點的發射信號覆蓋的節點集合。若節點可以設置不同的發射功率，那么節點u 和v

12、以d (u , v 為半徑的圓盤覆蓋的節點數可以認為等于IL(uv 的最小值（即uv 之間通信時實際干擾的下限），其度量公式如下。 minIL ( , , (, (, (, (, uv w w V u v d u w d u v or d v w d u v =（2）無線自組網采用多跳轉發組網方式。數據成功到達目的節點往往需要多次轉發，這就要求在轉發過程中，不能出現流內干擾和流間干擾，即路徑上所有節點不能互相干擾和受到其它路徑上節點的干擾。所以，本文結合路徑的長度（跳數）和每跳（邊）的干擾情形，提出基于路由協議的路徑干擾模型，并給出如下定義。定義2（路徑干擾）給定一個網絡拓撲圖G =(V ,

13、E ，節點u 和v 之間的路徑P uv e 1，e 2，, e k ,定義路徑P uv 干擾為：(IL( IP uve uv e P =（3） 目前，IETF 專門成立MANET 工作組提出的經典的無線自組網的路由協議（DSDV 和DSR ）都是選擇跳數較小的路由。本文用ISP (uv 表示節點uv 之間最短路徑的路徑干擾。同時文獻1516的仿真實驗表明：稀疏的拓撲結構大大降低了源節點到目的節點的所有路徑的條數，即降低了網絡的路由多樣性，如果存在多個路徑跳數長的數據流，它們匯聚到一個相同區域的概率相比在拓撲控制以前的網絡中選路時大了很多。這些區域從而成為“熱點區域”。 Fig. 1 The f

14、igures show the results of three different topology control algorithms being performed on theoriginal topology (a: the LIFE algorithm (b, the API algorithm (c, ISPT (d.圖1 針對初始拓撲結構，三種不同拓撲控制算法生成的拓撲圖。 如圖1所示，通過觀察在初始UDG 圖（未經拓撲控制處理）上分別運行LIFE 和API 算法生成的圖。（如圖1中的節點16）我們發現，“熱點”區域中的節點都有一個共同特點，就是它們不僅是其鄰居節點間互相連接

15、的唯一通道，如果從更大的區域來觀察，它們是幾個節點簇的連通關鍵點，也就是說，如果這些節點所在區域一旦出現長時間的流間干擾，將產生大量的路由開銷（參見本文第5節的仿真實驗），那么將使得多個節點簇中的節點無法相互正常通信；同時由于拓撲控制生成的網絡結構具有稀疏性，即使這些節點在全網中可能存在其它路徑（如圖1(b中，可以經過部署區域的上方的節點建立路徑），但跳數很大，路由算法運行開銷巨大，最終將影響網絡的傳輸能力。本文從拓撲結構的角度出發，對這些區域中的特殊節點定義如下。定義3（準干擾瓶頸節點）在一個拓撲圖中提取某個節點u 兩跳鄰居節點的拓撲子圖，那么u 是“準干擾瓶頸節點”，當且僅當在該子圖中刪除

16、u 以及連接u 的邊，原來u 節點的鄰居集被劃分成兩個或者多個不連通的非空集合。目前已提出的干擾最小化拓撲控制算法沒有考慮到稀疏化拓撲結構造成的干擾瓶頸節點增加的情況，也沒有設計針對性的處理策略。3 ISPT拓撲控制算法依據無線通信的特點，節點的信號發射功率和接收信號的閾值的不同有可能造成不同的干擾，即使自組網中節點的位置不變，節點設置不同的信號發射功率，構建的不同拓撲結構將有可能影響網絡的干擾程度。如何構建干擾最小化的網絡拓撲結構，是拓撲控制技術研究的一個關鍵問題。本文針對面向網絡傳輸性能最優化的干擾最小化拓撲控制NP 難問題5，提出了一個分(aUDG (b LIFE (c API (d I

17、SPT布式拓撲控制啟發式算法ISPT ，節點分布式獲取局部信息，采用啟發式策略構建干擾最小化的拓撲樹，在保證網絡連通的基礎上，使任意節點間的最短路徑干擾最小化；同時提出了一種準干擾瓶頸節點避免機制，通過減少拓撲結構中瓶頸節點的出現，避免路由造成的流間干擾概率增大對網絡傳輸性能的影響，最優化網絡吞吐量。文獻4指出設計一個有效實用的拓撲控制算法應滿足下列性質：1 算法在設置節點的最小發射功率的同時必須保證網絡連通；2 算法能分布式運行；3 算法簡單，且只需要每個節點收集自己局部的信息，從而減少信息的交互開銷，提高算法的收斂速度；4 算法生成的拓撲圖是對稱、邊稀疏、節點度有界的；5）算法生成的拓撲圖

18、具有Spanner 性質。基于以上性質，根據第二節定義的基于協議的網絡拓撲干擾模型，ISPT 算法主要由四個階段組成：信息收集、拓撲構建、功率設置和避免準干擾瓶頸節點的優化步驟。3.1 ISPT算法主要步驟3.1.1信息收集在信息收集階段，每個節點需要與其鄰近節點進行兩輪消息交互。利用鄰節點發現協議，節點以最大功率周期性地廣播Hello 分組。通過收集鄰近節點的Hello 消息中的節點ID 和位置等信息，每個節點u 可以獲得一跳最大可達鄰居集，記為1_MNBR(u 。節點然后進行第二輪Hello 消息交互，相互通告各自的一跳最大可達鄰居集，每個節點u 就可構建兩跳鄰居集，記為2_MNBR(u

19、。3.1.2拓撲構建每個節點各自獨立地進行拓撲構建。通過與鄰近節點之間交換信息，節點u 可以建立其本地最大功率拓撲結構，用一個無向有權圖max u G 表示，其中V(max uG = 1_MNBR(u U u ，E(max u G = ( i, j | ( i 1_MNBR( j and ( j 1_MNBR( i , i,j V(max u G ，對于max uG 中的每條邊（i, j），利用2_MNBR(u 中的鄰居集合，按照公式（2）計算干擾度，作為該邊的權值w(i, j。根據max uG ，節點u 執行單源最短路徑算法 (如Dijkstra 算法 求出以它為根的最短路徑樹Tree u

20、G ，值得注意的是，如果max uG 中有多條邊具有相同的權值，為了保證最短路徑樹的唯一性，當權值相等時，算法優先選取節點ID 小的邊。然后更新集合一跳邏輯鄰居集1_LNBR(u 為樹中u 的兒子節點。同時為了保證節點u 到max uG 中所有節點的最短路徑（最短路徑樹）中所有邊能存在于最后的拓撲子圖中，u 分別記錄其最短路徑樹中每個中間節點v 的兒子節點集合，并通過Hello 消息把該集合告知節點v ，也就是為了保證u 到每個節點的最短路徑都存在，希望其每個鄰近節點必須連通的節點集。3.1.3功率設置節點u 首先設置其數據通信時的傳輸功率為到達集合1_LNBR(u 中最遠的節點所需的功率。同

21、時為了保證鄰近節點通過u 到其它節點的路徑存在，在收到鄰近節點v 的Hello 通告時，提取出v 希望u 必須連通的節點集合加入1_LNBR(u 中，同時節點u 重新把功率設定為到達集合1_LNBR(u 中最遠的節點所需的功率。由于每條邊的兩個節點都會收到通告，該方式可以保證最終拓撲圖中邊的對稱性。3.1.4干擾瓶頸節點避免準干擾瓶頸節點的具體過程分如下幾步進行：（1） 采用與ISPT 算法第一步相同的消息交互方法，每個節點u 構建兩跳鄰居節點的拓撲子圖。（2） 按照準干擾瓶頸節點的定義判定自己是否滿足條件：如果除去u 和與u 直接相連的邊后的子圖2hops uG ，所有節點仍然連通，那么u

22、不是干擾瓶頸節點；否則u 是干擾瓶頸節點，進行下一步消除干擾瓶頸節點。（3） 采用加邊的方法消除干擾瓶頸節點。為了找到最“適合”加的邊，我們考慮如下原則：一是要保證u 的多個不連通的鄰節點集合連通；二是新增邊的干擾度小；三是增加的邊對節點u 的干擾小。在2hops uG 中選取任意節點對按照公式（2）計算干擾度作為權值，借鑒求解最小生成樹的Prim 算法（2hops u G 已有的邊依然保存），按照邊干擾度從小到大依次選取。為了減小增加的邊對節點u 的干擾，如果邊的兩個節點至少有一個不屬于1_LNBR(u 的優先選取，若選取的邊能連通兩個不連通的集合，則加入2hops u G 中，繼續選取過程

23、直到2hops uG 連通為止。 （4） 節點u 計算出所有新增的邊后，采用與ISPT 算法第三步相同的方法，通過Hello 通告的方式告知相應的節點，希望其改變功率設置以保證這些邊能夠建立。3.2算法分析和拓撲結構性質分析在進行拓撲控制時，每個節點各自獨立地運行ISPT 的四個步驟，所以ISPT 是一個完全分布式的算法。網絡中的每個節點獨立異步地運行該算法，在算法的第一步每對鄰近節點之間交互兩次，第三步交互一次，而準瓶頸節點處理步驟和第一步和第三步類似，需要交互三次。雖然節點異步執行，但由于每個節點僅僅只需與各自鄰近節點進行消息交互而無需轉發，利用CSMA/CA的沖突避免機制，所有節點可以在

24、一個常數時間區間內完成消息交互操作。交互消息的主要目的是使得每個節點獲取局部信息，用以構建一個僅由鄰近節點構成的拓撲子圖，顯見子圖中的節點數m 和邊數e 是遠小于整個網絡（即使網絡中有很多節點或者很密集），這使得每個節點在第二步運行最短路徑算法O (m 2 和第四步運行最小生成樹算法O (eloge 的實際運行時間代價很小。定義網絡所有節點以相同的最大功率構建的拓撲圖為G (V , E ，而由ISPT 構建的拓撲子圖為G = (V , E ，可證明該算法構建的拓撲圖是連通圖。定理1若初始拓撲圖G 是連通圖，那么G 也是連通圖。證明：不失一般性，隨機在圖中選取兩個節點u 和v ，由定義可知，兩個

25、節點在圖G 中一定連通。下面只需證明兩個節點在圖G 也一定雙向連通即可。在圖G 中根據u 和v 兩個節點相距的位置，可以分下面兩種情況：a ） 點u 和v 之間的距離小于最大功率覆蓋的距離，即在圖G 中u 和v 存在邊。那么兩個節點在運行ISPT 算法第二步時，都會把對方作為拓撲子圖中的一個節點。那么也一定會求出到對方的干擾度最小的路徑，并發出消息通告路徑上的節點，以保證在最終的圖G 中路徑上所有的雙向邊都存在。b ） 節點u 和v 之間的距離大于最大功率覆蓋的距離，即在圖G 中u 和v 之間不存在邊，但一定存在一些中間節點v 1, v 2, v 3, , vk 使u 和v 之間存在雙向連通的

26、路徑L uv 。根據初始拓撲圖的定義，該路徑上任意兩個相鄰節點之間的距離小于最大功率覆蓋的距離。那么根據情況（a ）的分析，在圖G 中兩個相鄰節點之間一定存在雙向連通路徑。由此，在圖G 中u 和v 之間一定存在雙向連通的路徑。綜合上述兩種情況的分析，可以證明ISPT 算法可以保證G 是連通圖。 證畢推論1 圖G 任意兩點的干擾度最小的路徑，在圖G 依然存在，即圖G 具有干擾度的擴展因子有界的特性。證明：根據最短路徑的性質，任意兩個節點u 和v 之間的最短路徑經過i 點，那么u 到i 的最短路徑一定也是沿著這條最短路徑的軌跡。對于圖G 節點u 和v 之間的干擾度最短路徑上的所有邊，都將被路徑上的

27、所有點執行ISPT 算法第二步構建最短路徑樹時求出，并通過第三步消息通告以保證存在與圖G 中。而ISPT 算法的第四步處理準瓶頸節點是加邊操作，對最短路徑不會產生影響。由于ISPT 可以保證干擾度最小的路徑的存在，按照spanner 擴展因子的定義4可知推論成立。 證畢由上述分析可知，ISPT 算法具有分布式、基于局部信息、算法簡單、消息開銷小、擴展性好和收斂快的特點。同時證明算法構建的拓撲圖不僅是連通圖，而且是任意節點間的最短路徑干擾最小化的拓撲圖。 4 性能仿真評估 性能仿真 仿真評估 為了評估 ISPT 算法的有效性，基于最大發送功率構建的初始拓撲結構（簡稱 UDG） ， 計算并比較算法

28、 LIFE、API 和 ISPT 導出的拓撲圖的干擾值，在此基礎上，采用網絡仿真平 臺，比較并分析了不同算法生成的拓撲結構對網絡性能的影響。 4.1 網絡拓撲結構干擾值比較 本文使用平均邊干擾（公式 2）和平均最短跳數路徑干擾（公式 3）作為拓撲圖干擾的 評估參數。 仿真的區域為 1000×1000， 節點數從 50 到 250， 節點的初始最大傳輸半徑為 250， 每個特定的節點數， 節點在仿真區域中均勻隨機分布生成 1000 個網絡場景。 對于每個場景， 分別運行三種拓撲控制算法，對其拓撲結構的干擾值進行計算后取平均值。 圖 2 給出了隨著網絡節點數增加， 四種拓撲結構的平均邊干

29、擾的變化趨勢。 如圖 2 所示， 與 UDG 圖相比，三種拓撲控制算法顯著減小了網絡中邊的干擾，而且隨著節點數的增加， 拓撲控制后的拓撲圖的平均邊干擾增長幅度較慢。LIFE 算法生成的拓撲圖的邊干擾是最小 的。與 API 算法相比，ISPT 算法生成的拓撲圖的邊干擾較小。 圖 3 給出了隨著網絡節點數增加，四種拓撲結構的平均最短跳數路徑干擾的變化趨勢。 如圖 3 所示， ISPT 算法生成的拓撲圖是平均最短跳數路徑干擾最小的， LIFE 和 API 并沒 而 有有效的降低最大功率拓撲圖的最短跳數路徑的干擾值。 通過仿真實驗驗證了本文 3.2 節的分析，基于最短干擾路徑樹的 ISPT 算法有效的

30、降低 了網絡的整體干擾，相對于基于邊干擾優化的 LIFE 算法和基于 GG 圖進行局部路徑優化的 API 算法，將更有效地控制通信過程中的干擾。 40 35 30 25 20 15 10 5 0 50 LIFE API ISPT UDG 平均最短跳數路徑干擾 70 60 50 40 30 20 10 50 100 150 節點數(個 200 250 LIFE API ISPT UDG 平均邊干擾 100 150 節點數(個 200 250 Fig. 2 The average edge interference 圖 2 平均邊干擾比較 Fig. 3 The average shortest-h

31、op path interference 圖 3. 平均最短跳數路徑干擾比較 4.2 網絡拓撲結構對網絡性能的影響 我們采用當前流行的網絡仿真軟件 OPNET10.5 作為仿真平臺，定量分析干擾優化拓撲 控制算法對無線自組網性能的影響。根據上述拓撲圖特性的仿真實驗可知，節點數在 50 到 250 之間，各種算法生成的拓撲圖特性變化趨勢穩定。本文取 160 個節點隨機分布在 1000m ×1000m 的二維區域中，仿真場景設置如下：每個節點傳播損耗模型使用自由空間模型，使 用 0dB 增益的全向天線，天線高度為 1.5m，接收閾值為-80dbm，節點初始最大發射功率為 0.0064W(

32、此時每個節點傳輸半徑為 250m。 每個節點在鏈路層和網絡層分別使用基于 802.11 標準的 MAC 協議和 DSR 路由協議。每個 CBR 數據流的源節點和目的節點隨機選擇，數據 包的大小為 1K 字節，每個源節點產生分組速率(單位為 packets/s從 0.25 到 2.5，發送間隔 時間服從泊松分布。仿真時間為 500s。仿真中，根據節點最大功率構建的初始拓撲結構（簡 稱 UDG）和 3 種不同拓撲控制算法（LIFE、API 和 ISPT）生成的拓撲結構，設置每個節點 的發射功率。對于每一個拓撲結構，設置 CBR 數據流從 20 個增加到 50 個。我們統計了 10 次仿真后的結果，

33、取平均值，比較不同業務負載下 4 種不同結構網絡的傳輸性能，即在不同 業務負載下的網絡分組交付率的變化，交付率是指網絡總接收數據量和總發送數據量的比 值，可以反映網絡的數據傳輸效率。 仿真結果發現，對于每一個拓撲結構，隨著數據流數量的增加和發包速率的增加，網絡 的傳輸性能表現出逐漸下降的趨勢。而對于相同數據流的數量，隨著發包速率的增加，4 種 不同拓撲結構對網絡性能的影響趨勢和比較結果相同，本文取 40 個數據流的仿真結果進行 具體描述和分析。 4 和圖 5 分別給出了隨著網絡負載的增加， 圖 四種拓撲結構對網絡路由請 求包數和網絡分組交付率影響的變化趨勢。 由圖 4 可知，當負載較低時（網絡

34、負載小于 10 包/秒） ，路由請求數小，說明網絡中的 通信碰撞概率較低，路由穩定且開銷小。如圖 5 所示，網絡的吞吐率接近 100%，有無拓撲 控制對網絡的性能影響不是很大。但是，由 4.1 節的實驗可知 LIFE 算法構建的網絡是最稀 疏的，所以即使網絡流速小，但由于網絡流數多，經過路由后，匯聚到相同的干擾瓶頸節點 區域造成分組競爭信道失敗的概率變大，引起 DSR 路由協議不斷重新進行路由請求，如圖 4 所示，LIFE 算法生成的拓撲圖在低負載時，路由請求包數是其余三種結構的 5 倍，大量 的路由開銷降低業務流的端到端通過量。 這說明按照局部干擾最小化思想設計拓撲控制算法 會造成網絡拓撲過

35、于稀疏， 增加了路徑長度和流間干擾， 最終并不能有效地優化網絡傳輸能 力。 如圖 4 所示，隨著網絡負載的增加，各個分組同時競爭信道的概率變大，而分組對信道 競爭的加劇會使得鏈路失敗概率增加，導致 DSR 路由協議不斷尋找新的路由，產生大量的 路由開銷，如圖 5 所示，業務流的端到端通過量從而顯著降低。由 4.1 節的實驗可知，按照 路徑和全局網絡最小化干擾思想設計的 API 和 ISPT 算法構造的拓撲結構，即減小了局部干 擾，又保證了路徑長度穩定，也就減小了路徑干擾，如圖 5 所示，與 UDG 相比，提高了空 間復用度， 增加了網絡吞吐率。 其中 ISPT 算法由于可保證生成的拓撲圖中路徑

36、干擾最小 （證 明見 3.2 節） ，與 API 算法相比，網絡吞吐率提高了約 10%。 16000 14000 1 路由請求包數(packets 12000 10000 8000 6000 4000 2000 0 分組交付率(% ISPT API LIFE UDG 0.8 0.6 0.4 0.2 0 ISPT API LIFE UDG 10 20 30 40 50 60 70 80 90 100 網絡輸入流量(packets/s 10 20 30 40 50 60 70 80 90 100 網絡輸入流量(packets/s Fig. 4 Routing overhead obtained f

37、rom CBR flows Fig. 5 Fraction data Pks delivered obtained from at various loads 圖 4 在不同業務負載下的路由請求包數比較 CBR flows at various loads 圖 5 在不同業務負載下的分組交付率比較 5 結論 本文主要研究了如何定義并降低自組網中的干擾以提高網絡傳輸能力的問題。 通過分析 現有的拓撲控制算法及其存在的局限性， 從拓撲結構的角度提出新的干擾度量方法； 在此基 礎上給出干擾最小化拓撲控制算法ISPT。與其它的干擾模型相比，新的基于協議的干擾 模型兼顧了鏈路通信的干擾情形和整個路徑上多

38、跳轉發時的流內和流間干擾， 更全面直觀地 反映現實網絡的干擾情形。分布式算法ISPT的主要特點是獲取算法執行所需數據的代價小， 且算法運行簡單快速。該算法從全局的觀點出發，更注重對網絡的整體干擾的控制，而不是 只關注某些局部或者特殊情形下的干擾， 在保證網絡連通的前提下使網絡的路徑干擾盡量最 小，并且通過在ISPT中加入準干擾瓶頸節點避免機制，較好地避免了在稀疏網絡中路由瓶 頸問題造成的流間干擾概率增大現象。 仿真結果說明， ISPT算法與未經拓撲控制及已有的干 擾最小化拓撲控制算法LIFE、API相比，更好地改善了網絡的性能。 由于干擾與網絡負載情況和網絡協議簇的機理緊密相關， 因此僅僅在網

39、絡實際應用前運 用拓撲控制優化拓撲結構還不夠。 在下一步的工作中， 我們將研究感知網絡負載狀態的自適 應拓撲控制技術以及干擾瓶頸節點處理技術， 并在協議簇各層上采用干擾最小化技術進一步 提高網絡的性能。 參考文獻： 參考文獻： 1 Goldsmith A J, Wicker S BDesign challenges for energy-constrained Ad Hoc wireless networksJIEEE Wireless Communications, 2002, 9(4: 8-27. 2 SHEN Zhong, CHANG Yi-Lin, et al. A Distribut

40、ed Topology Control Algorithm for Self-Maintenance of the Minimum-Energy Property of a Wireless Networks TopologyJ. Chinese Journal of Computers, 2007, 30(4: 569-578. 沈中等. 一種建立可自維護且具有最小能 量特性的無線網絡的分布式拓撲控制算法. 計算機學報, 2007, 30(4: 569-578. 3 P. Santi. Topology Control in Wireless Ad hoc and Sensor Networ

41、ksJ. ACM Comp. Surveys. 2005, 37(2: 164194. 4 Lu Gang, Zhou Mingtian, Niu Xinzheng, et al. A Survey of Proximity Graphs in Wireless NetworksJ. Journal of Software, 2008, 19(4: 888911. 路綱等. 無線網絡臨近圖綜述J. 軟件 學報, 2008, 19(4: 888911 5 Davide Bilo, Guido Proiettib. On the complexity of minimizing interfere

42、nce in ad-hoc and sensor networksJ. Theoretical Computer Science, 2008, 402(1: 43-55. 6 K. Moaveni-Nejad and X. Li. Low-interference topology control for wireless ad hoc networksJ. Ad Hoc & Sensor Wireless Networks: An International Journal, Volume 1, Number 1-2, 2005: 41-64. 7 P. von Rickenbach

43、, S. Schmid, R. Wattenhofer, A. Zollinger. A robust interference model for wireless ad-hoc networksC/ Proceedings of 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN, USA, 2005:239-247. 8 Magnús M. Halldórsson, Takeshi Tokuyama. Minimizing interference of a wireless ad-hoc network in a planeJ. Theoretical Computer Science archive, 2008, 402(1: 29-42. 9 M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger. Does Topology Control Reduce Interference?C/ Proceedings of 5th ACM Int.