一種最小化無線自組網(wǎng)干擾的拓撲控制算法

1、一種最小化無線自組網(wǎng)干擾的拓撲控制算法李曉鴻1，張大方2，蔡小莉1，王 東1(1. 湖南大學計算機與通信學院，湖南 長沙 410082；2. 湖南大學軟件學院，湖南 長沙 410082 摘 要:針對無線自組網(wǎng)中，如何準確度量干擾并構建干擾最小化的網(wǎng)絡結構的問題。根據(jù)無線通信的特點和網(wǎng)絡協(xié)議的機制，設計了一種基于協(xié)議的網(wǎng)絡干擾模型度量方法，并提出了一種啟發(fā)式的干擾最小化拓撲控制算法，該分布式算法能保證網(wǎng)絡連通，并使整個網(wǎng)絡中節(jié)點間的路徑干擾最小化。仿真結果驗證了新算法降低了網(wǎng)絡沖突，更好地改善了網(wǎng)絡性能。關鍵詞: 自組網(wǎng); 拓撲控制; 干擾; 吞吐量中圖法分類號: 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引言自組網(wǎng)是一種無中心、自組織的多跳無線網(wǎng)絡。由于其具有抗毀性、自組織性與機動性等特點，將在無線通信領域發(fā)揮越來越重要的作用。為保證無線自組網(wǎng)能即時、通暢和高效通信，提高自組網(wǎng)的傳輸能力和減少節(jié)點的能耗是自組網(wǎng)面臨的關鍵問題12。拓撲控制是提高網(wǎng)絡吞吐率和延長網(wǎng)絡生命周期的一種重要途徑。該技術通過調整節(jié)點的發(fā)送功率和建立合適的相鄰關系，構建全局優(yōu)化網(wǎng)絡拓撲。其主要目標是降低節(jié)點能耗和減少通信干擾，為MAC 協(xié)議和路由協(xié)議的順利執(zhí)

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

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

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

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

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

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

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

13、E ，節(jié)點u 和v 之間的路徑P uv e 1，e 2，, e k ,定義路徑P uv 干擾為：(IL( IP uve uv e P =（3） 目前，IETF 專門成立MANET 工作組提出的經(jīng)典的無線自組網(wǎng)的路由協(xié)議（DSDV 和DSR ）都是選擇跳數(shù)較小的路由。本文用ISP (uv 表示節(jié)點uv 之間最短路徑的路徑干擾。同時文獻1516的仿真實驗表明：稀疏的拓撲結構大大降低了源節(jié)點到目的節(jié)點的所有路徑的條數(shù)，即降低了網(wǎng)絡的路由多樣性，如果存在多個路徑跳數(shù)長的數(shù)據(jù)流，它們匯聚到一個相同區(qū)域的概率相比在拓撲控制以前的網(wǎng)絡中選路時大了很多。這些區(qū)域從而成為“熱點區(qū)域”。 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 圖（未經(jīng)拓撲控制處理）上分別運行LIFE 和API 算法生成的圖。（如圖1中的節(jié)點16）我們發(fā)現(xiàn)，“熱點”區(qū)域中的節(jié)點都有一個共同特點，就是它們不僅是其鄰居節(jié)點間互相連接

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

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

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

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

19、。3.1.2拓撲構建每個節(jié)點各自獨立地進行拓撲構建。通過與鄰近節(jié)點之間交換信息，節(jié)點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。根據(jù)max uG ，節(jié)點u 執(zhí)行單源最短路徑算法 (如Dijkstra 算法 求出以它為根的最短路徑樹Tree u

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、干擾最小 （證 明見 3.2 節(jié)） ，與 API 算法相比，網(wǎng)絡吞吐率提高了約 10%。 16000 14000 1 路由請求包數(shù)(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 網(wǎng)絡輸入流量(packets/s 10 20 30 40 50 60 70 80 90 100 網(wǎng)絡輸入流量(packets/s Fig. 4 Routing overhead obtained f

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

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

39、絡實際應用前運 用拓撲控制優(yōu)化拓撲結構還不夠。 在下一步的工作中， 我們將研究感知網(wǎng)絡負載狀態(tài)的自適 應拓撲控制技術以及干擾瓶頸節(jié)點處理技術， 并在協(xié)議簇各層上采用干擾最小化技術進一步 提高網(wǎng)絡的性能。 參考文獻： 參考文獻： 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. 沈中等. 一種建立可自維護且具有最小能 量特性的無線網(wǎng)絡的分布式拓撲控制算法. 計算機學報, 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. 路綱等. 無線網(wǎng)絡臨近圖綜述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.