優化目標可變的容錯三維拓撲控制算法＊

王 東，鄧 好

（湖南大學信息科學與工程學院，湖南長沙410082）

1 引言

Ad Hoc網絡是指由一組自治無線設備組成的支持多跳的臨時性的網絡系統。網絡中的所有節點在共享的無線信道上互相通信，無需任何網絡基礎設施，且具有易于快速部署的特點，使其在應急通信、交通管理、現代化生產、醫療衛生、環境監測等領域中得到廣泛應用。因此，Ad Hoc網絡通信技術受到了研究人員的廣泛關注。

無線網絡的拓撲結構是基于節點的物理位置和信號傳輸范圍自治形成的［1］。在Ad Hoc網絡中，一方面，節點的物理位置由任務需求來確定，另一方面，節點的信號傳輸半徑可以根據需求進行調節。如果所有節點都以最大傳輸功率工作，節點有限的能量將被通信部件快速消耗，造成節點過早死亡，使得網絡局部斷開，甚至網絡不連通；另外，節點以最大功率傳輸會使得節點信號彼此過度重疊，造成無線信號互相干擾，影響節點的通信質量，降低網絡的吞吐率。為了有效解決以上問題，在Ad Hoc網絡中有必要針對任務需求，對節點的傳輸功率進行調節，從而對無線網絡的拓撲進行控制。

由于Ad Hoc網絡中節點能量受限，節點工作一段時間后將會死亡，另外，任務需求也可能使節點發生移動，所以Ad Hoc網絡中節點加入和離開網絡等異動情況是經常發生的。節點的頻繁異動使得網絡拓撲結構動態變化，從而對網絡的性能（如節點能耗、網絡傳輸能力等）產生很大的影響。此外，在實際應用中，網絡的通信場景會發生變化，當多個節點同時通信或部分節點發送大量數據時，其信號不間斷，會對其他節點造成干擾，造成網絡通信質量下降，此時降低干擾尤其重要；當節點不同時通信或節點發送數據少時，信號沖突幾率低，干擾對網絡影響不大，此時，拓撲控制優化目標應該以節約能量、延長網絡生命周期為主。因此，如何研究出一種具有較好拓撲容錯能力，能適應實際通信場景變化，同時能兼顧其它網絡性能要求的拓撲控制算法成為Ad Hoc網絡技術研究的熱點。

本文提出一種適用于三維立體空間、可以根據網絡干擾情況調整優化目標并且具有較好容錯能力的拓撲控制算法——OVFSS（Optimization－Variable Fault－tolerant Spanning Subgraph）。

2 相關工作

早期的拓撲控制是通過調整節點發射功率在保持連通性的同時達到節能的目的，從而延長網絡生命周期。Chew L P［2］第一次提出了伸展因子的概念，該因子等于通過拓撲控制技術調整后的生成子圖路徑能耗與原圖路徑能耗之比，來描述拓撲控制之后網絡的能量伸展性。近期，一些研究工作也把注意力放到如何調節功率，使網絡保證連通的情況下同時滿足能量伸展性。

Wang Y等人［3］最先開始研究如何通過減小節點的發送功率來降低網絡總能耗，并且使調整后的通信子圖具有能量伸展性。同時，他們還提出了兩種啟發式算法，使構建的網絡能耗較低，且滿足能量伸展性等要求。

Shpungin H等人［4］從理論上研究了伸展性問題，他們的目標是同時滿足能量伸展性和距離伸展性。為了能量伸展性，他們提出了一種方法，使調整后的子網的能量伸展因子為2（即新導出的子圖點對之間的路徑能耗最多是原圖的2倍），并且得到的子網是強連通的。

Rickenbach P V［5］提出降低網絡干擾才是無線網絡拓撲控制最重要的目標。無線網絡中的干擾會導致網絡擁塞和數據包的重傳，對網絡的生命周期和網絡的可用性都有很大的影響。

上述工作主要考慮無線網絡的能量有效性和如何延長網絡的生命周期問題，而網絡的容錯能力也十分重要。無線網絡的容錯拓撲控制主要研究如何構建k連通的拓撲結構圖，即在k－1個節點失效的情況下，網絡仍然保持連通，相關的研究有文獻［6～8］。但是，這些研究又缺少對其他性能的考慮，例如能量有效性等。

在無線網絡領域，研究的重點集中在節能、減小干擾、容錯等方面。為了簡化算法研究，方便建模，一般假設網絡部署在二維平面上。然而，實際應用時網絡節點一般是分布在三維立體空間里。二維平面圖和三維立體圖在性質上有很大的差別，簡單地將三維網絡映射到二維會丟失許多幾何性質，所以二維場景下設計的部分算法無法直接應用到三維。為了設計出更加真實、合理有效且可應用到實際網絡中的拓撲控制算法，Wang Y等人［9］在三維場景下對無線網絡的拓撲控制進行研究，他們提出了3D k－RNG、3D k－GG和3D k－YG三種算法，并且證明這些算法都具有一定容錯能力，同時還分別滿足部分網絡性能指標。

由于三維場景的特殊性，針對三維場景所研究的拓撲控制算法還不多，面對Ad Hoc網絡可能部署的復雜環境，追求單一優化目標或是固定優化目標的算法的實用性值得懷疑。為了算法的靈活多變性，本文提出一種優化目標可改變的容錯拓撲控制算法。

3 數學模型

無線網絡結構一般將其抽象成圖，拓撲控制技術通過調節節點發射功率使得節點信號覆蓋范圍變化，影響節點之間的連通，可以抽象為圖中邊的增刪。需要滿足的網絡性能要求，例如連通度、容錯能力、干擾較小等，都可以抽象為對圖的性質要求，對應為圖的連通度、k連通、點干擾、邊干擾等。

本文研究針對的是較為真實的三維應用場景，假設三維的Ad Hoc網絡分布在一個三維空間R3上。網絡用無向圖G＝（V，E）表示，其中，V表示網絡中所有節點組成的集合，E表示網絡中所有邊組成的集合。用｜V｜表示網絡中的節點數，｜E｜表示網絡中的邊數。每個節點的發射功率都可以設置為從0到最大值Tmax之間的任意值。每個節點均有一個id號（IP或者MAC地址）。三維Ad Hoc網絡的模型是個單位球UBG（Unit Ball Graph）。當且僅當u和v之間的歐氏距離dist（u，v）均不大于最大發射信號距離r時，u和v之間存在一條邊。

無線信號在傳播過程中信號會衰減，無線信號傳播模型決定了節點發射功率和接收功率的關系。信號功率的衰減與發射天線和接收天線之間的距離的β次方成正比［10］，β是一個常數，取值范圍由環境所決定，一般為2～5。β的取值與無線傳播模型相關，對于自由空間模型，認為無線電波的損耗只和傳播距離和電波頻率有關系，在給定信號頻率的時候，只和距離有關系。本文研究時采用該模型，取值β＝2，即給定信號頻率時，電波損耗與傳播距離的平方成正比。

對于節點集合V中的兩個節點u和v，給出節點傳輸能耗、k連通、點干擾、邊干擾的定義。

定義1 點u是圖G中的一點，拓撲控制后，u的傳輸能耗為該節點能達到的最遠距離鄰居節點所需的能耗。

定義2 當且僅當圖G＝（V，E）中的任意兩點u和v之間存在頂點不相交的k條路徑時，圖G＝（V，E）是k連通的。也可以理解為，當去掉圖G＝（V，E）中k－1個頂點，圖仍然連通時，圖G＝（V，E）是k連通的。

節點之間通信造成的干擾是一種概率性事件，為了能量化網絡中的干擾，借鑒文獻［11］定義干擾模型。節點u和v通信時，若存在節點w，且該節點w的發射區域覆蓋了u或者v，則w的信號會影響u的發送或者v的接收，此時就可以理解為w對u或v造成了干擾。借鑒二維網絡中經典的干擾模型，本文構建一種三維網絡內節點通信干擾模型，定義如下：

定義3 節點u的干擾值I（u）定義為所有通信范圍覆蓋了節點u的節點數。I（u）＝｛v｜v∈V＼｛u｝，u∈Z（v，rv）｝，這里V表示網絡圖節點集合，Z（v，rv）代表以節點v為中心、rv為半徑的球形通信區域。

定義4 邊e＝（u，v）的干擾值可以定義為所有通信范圍覆蓋了邊e中節點u或v的節點數。I（e）＝｛w｜u∈Z（w，rw）∪v∈Z（w，rw），e＝（u，v），w∈V｝。

圖1為三維網絡邊干擾模型示意圖，每個節點均以其發射功率能達到的通信距離為半徑形成一個球狀通信區域，假設節點u和節點v之間存在一條邊，若節點u或v處于節點w的通信區域內，認為節點w對節點u、v之間的通信邊造成干擾，該邊的邊干擾值加1，以此方法檢查所有鄰居節點，最終得出該邊的邊干擾值。

Figure 1 Edge interference model in three－dimensional network圖1 三維網絡邊干擾模型

4 優化目標可變容錯拓撲控制算法

實際應用的Ad Hoc網絡拓撲控制算法需要綜合考慮多個優化因素。以往的算法考慮多個優化目標時，由于各個優化目標（例如網絡干擾和能耗）可能是互相矛盾的，一般在各項網絡性能指標中取一個折衷值，部分優化干擾和部分優化能耗，是一種非最優化的靜態平衡。實際情況下，網絡通信狀態是變化的，某時刻可能大量節點同時通信或部分節點發送大量數據，其信號對其他節點造成干擾，也可能某時刻節點處于監聽狀態，偶爾發送數據，彼此信號沖突較小，干擾較小。靜態優化并不能適應這種變化情況，無法將優化目標最大化。針對應用場景通信環境信號干擾強烈程度多變的情況，提出一種優化目標可變的容錯拓撲控制算法OVFSS，在保證網絡k連通的前提下，根據節點通信情況判斷網絡所處情況，選擇合適的參數，進行有針對性的目標優化。算法的具體思想是，根據網絡通信情況，適當選擇重點優化的目標。在干擾影響較大時優先減小干擾，保證網絡應用能有效實施；在干擾影響較小時，不考慮干擾，優先降低能耗，以便延長網絡生命周期。

文獻［11］通過對干擾進行建模，將概率性事件進行量化。同樣的路由算法下，當節點同時通信或部分節點發送大量數據時，數據沖突加劇，丟包、重傳次數會上升，此時干擾對網絡影響較大；當節點不同時通信或節點發送數據小，彼此信號沖突概率低時，丟包、重傳次數會較小，此時干擾對網絡影響較小。本文假設節點設備硬件和協議能通過重傳、丟包等數據的統計，判斷網絡的干擾影響程度，干擾影響大時設置參數s＝1，干擾影響小時設置參數為s＝0。

為了減小網絡中的干擾，可將邊權值改為邊干擾值，但同時也發現一個問題，如圖2所示I（A，B）＝I（A，C）＝3，但此時鄰居節點距離不相同，圖2中可見，dist（A，B）＞dist（A，C），即單一考慮將邊權值改為邊干擾值考慮不周全。

Figure 2 The case of same edge interference but different distances圖2 邊干擾相同距離不同情況

為此，OVFSS算法將綜合考慮干擾和距離能耗等因素，定義邊權值如下：

權值公式由兩部分組成，第一部分是干擾影響值，第二部分是規格化后的距離影響值。s＝1時，權值公式主要由邊干擾I（u，v）決定，同時規格化距離值能保證在節點干擾度相同的情況下，距離小的邊權值較小；s＝0時，即干擾較小時，邊干擾不納入考慮，由規格化距離值決定權值，最大化地實現節能優化的目標。

要注意的是，尋找最小能耗生成子圖已被證明是NP難問題，本算法考慮容錯和多個優化目標時該問題顯然也是NP難問題。

OVFSS算法根據邊權值公式對圖中所有的邊的權重進行計算，然后按照邊權值升序排列。根據得到的邊權值，基于貪婪算法計算一個干擾最小的或能耗最小的k連通圖。為保證貪婪算法是唯一結果，假設不相同的節點對之間的邊權值沒有相同的。算法的偽代碼如下：

算法1 OVFSS

輸入：具有N個節點的點集和連通度k（k≥1）。

輸出：k連通的干擾最小或能耗最小的子圖。

1：初始化原圖G＝（V，E）。

2：計算G中每條邊的邊權值W＝s×I＋dist/r。

3：將所有的邊按照邊權值升序排列。

4：初始化子圖GOVFSS＝（V，EOVFSS＝?）。

5：對于圖中的每條邊e＝（u，v）。

6： 如果GOVFSS中u和v之間不是k連通

7： 添加該邊到邊集合中EOVFSS＝EOVFSS∪｛e｝；

9： 如果所有節點之間均是k連通

10： 退出，算法結束

當s＝0時，權值由距離決定，算法等價于Kruskal算法［12］的一種擴展版。該算法在保證容錯的前提下，選取距離最短邊以尋求節能優化，其干擾優化能力不強（本身就是在干擾較小的情況下才選擇該算法）。

當s＝1時，邊干擾值起決定作用，算法以干擾優化能力為主，同時兼顧選取距離較短、能耗較低的邊，算法的優勢體現明顯。

下面對算法的正確性給出證明，即證明算法保證網絡k連通的情況下優化網絡干擾，使其干擾最小化，并同時考慮了節能。為了方便證明，本文采用以下術語：

G代表初始的拓撲圖，G′代表算法優化后最終的拓撲圖。Path（u，w1，w2，…，wn，v）表示從節點u到節點v的路徑，其中w1，w2，…，wn代表路徑經過的節點。Suv（G）代表無向圖G中節點u到節點v之間的所有不相交的路徑數。

引理1 設u1和u2是k連通無向圖G中兩節點，如果u1和u2間存在邊（u1，u2），并且在圖G中移除邊（u1，u2）后，u1和u2之間仍然是k連通，那么G－（u1，u2）仍然是k連通的。

證明 要證明G－（u1，u2）是k連通的，等價于證明G′＝G－（u1，u2）中移除k－1個節點后，圖G′仍然是連通的。不失一般性，假設｛u1，u2｝∩｛v1，v2｝＝?。如果能夠證明在圖G′中移除k－1個節點后，任意兩個節點v1、v2仍然連通，那么就可以證明G′是k連通的。

(4) 交通銜接條件：站點周邊地區的交通可達性以及車站接駁體系的成熟程度，是制約客流的主要因素。本文主要選取車站周邊道路網密度、人行道面積率、出入口周邊機動車及自行車停放場地面積、公交車站經停線路數等指標，經過同等權重的無量綱化處理得到交通銜接水平評價值。

（1）如果v1、v2兩個節點在原圖G中直接相連，因為原圖G是k連通的，那么很顯然在圖G′中移除k－1個節點后，節點v1、v2仍然是連通的。

（2）如果v1、v2兩個節點在原圖G中并沒有邊相連。假設圖G″為G′－（k－1）個節點后的圖。S1表示在G′中移除k－1個節點后Sv1v2（G′）中斷開的路徑數。因為Sv1v2（G′）是圖G′中v1、v2兩節點的不相交的路徑數，所以在圖G′中移除k－1個最多斷開k－1條v1、v2節點間的路徑，因此S1≤k－1。

①如果Sv1v2（G′）≥k，那么Sv1v2（G″）≥Sv1v2（G′）－S1≥k－（k－1）≥1。所以，在圖G″中，v1、v2兩個節點是連通的。

②如果Sv1v2（G′）＜k，這種情況只可能是在原圖G中刪除邊（u1，u2）的時候斷開了節點v1和v2之間的一條路徑。所以，可以得到Sv1v2（G′）＝k－1。現在再考慮在圖G′中刪除k－1個節點后的兩種情況。

a如果S1＜k－1，那么Sv1v2（G″）≥Sv1v2（G′）－S1≥1，即節點v1、v2兩個節點是連通的。

b如果S1＝k－1，因為節點間的路徑都是不相交的，S1＝k－1這種情況唯一的出現場景為v1與u1直接相連，v2和u2直接相連。用S2表示在G′中移除k－1個節點后Su1u2（G′）中斷開的路徑數，由命題題意可知Su1u2（G′）≥k，并且很容易知道S2≤k－1，這也就證明了在G″中u1和u2是連通的，又因為v1、v2分別與u1、u2相連，所以v1，v2是連通的。

綜上可得，G′是k連通的，因此G－（u1，u2）是k連通的。證畢。□

引理2 假設無向圖H和H′滿足條件V（H）＝V（H′）。如果H是k連通的，并且每條邊（u，v）∈E（H）－E（H′）在圖G－｛（u0，v0）∈E（H）：W（u0，v0）≥W（u，v）｝中都是k連通的，那么H′也是k連通的。

證明 用集合E＝E（H）－E（H′）＝｛（u1，v1），（u2，v2），…，（um，vm）｝表示在圖H中出現且在圖H′沒有出現的邊集，且W（u1，v1）＞W（u2，v2）＞…＞W（um，vm）。同時定義一系列原圖H的子圖Hi：H0＝H，Hi＝Hi－1－（ui，vi）。下面用歸納法來證明：

（1）H0＝H，所以H0是k連通的。

（2）如果Hi－1是k連通的，那么應用引理1可得Hi是k連通的。所以，可以得到Hm是k連通的。

因為E（Hm）?E（H′），所以H′也是k連通的。證畢。□

定理1 G′是k連通的。

證明 在OVFSS算法中，所有的邊都是按非遞減順序排列的，而且沒有加入圖G′中的邊唯一的條件就是這條邊的兩個節點間已經是k連通的。應用引理2可以得到圖G′是k連通的。證畢。□

定理2 優化干擾時，G′是一個干擾最小的k連通圖。

證明 s＝1時，權值公式主要由邊干擾值確定，邊權值可以近似為邊干擾值，用Sk（G）代表圖G的所有k連通子圖。如果G是k連通的，根據定理1，可得G′也是k連通的。假設邊（u，v）是OVFSS算法中最后加入圖G′的一條邊。那么可以知道I（u，v）＝Max（u0，v0∈E（G′）｛I（u0，v0）＜I（u，v）｝，即I（u，v）的干擾值比已經加入到圖G′中的任何一條邊的干擾值都大。設G2＝G′－（u，v），因此在圖G2中節點u和節點v之間的不相交路徑數是小于k的，否則OVFSS算法不會將邊（u，v）加入到圖G′中。用圖C＝（V（C），E（C）），這里V（C）＝V（G），E（C）＝｛（u0，v0）∈E（G）：I（u0，v0）＜I（u，v）｝。如果可以證明C并不是k連通，那就可以說在圖G的任何一個k連通子圖中都存在一條邊的干擾值大于I（u，v），這也證明了G′是干擾最小的k連通子圖。

用反證法證明C不是k連通的。假設C是k連通的，因此Suv（C）≥k。那么E（C）?E（G2）；否則，｜Suv（G2）｜≥｜Suv（C）｜≥k，與前段中G2的定義矛盾。因此，E0＝E（C）－E（G2）≠?。因為所有的邊都是按干擾值非遞減順序加入到圖G′中的，所以有?（u1，v1）∈E0都滿足u1和v1在圖C－｛（u0，v0）∈E（C）：I（u0，v0）≥I（u1，v1）｝中是k連通的。由引理2可得，當把E0中的所有邊都刪除后，節點u和節點v之間仍然是k連通的，也就是說｜Suv（G2）｜≥k，而這與G2的定義是矛盾的。所以，由OVFSS算法得到的G′是原圖G的干擾最小k連通子圖。證畢。□

定理2證明了圖G′是干擾最小的k連通圖，在權值公式里，在干擾相同的情況下，選取邊長更短的邊，兼顧節能，以延長網絡生命周期。在干擾較小時，權值公式改為由能耗決定邊權值，此時通過類似定理2的證明過程可以得出，優化能耗時G′是一個能耗最小的k連通圖。

5 仿真實驗

考慮到3D k－GG算法和3D k－YG算法解決的問題與本文研究問題最為接近且是本領域具有代表性的算法，下面對OVFSS算法、3D k－GG算法和3D k－YG算法在干擾優化方面進行比較。

實驗場景［8］為20×20×20的三維空間，節點的最大發射功率為9，節點數從50到175遞增，β值取2。實驗分別比較了干擾較強（s＝1）時不同容錯度k＝1，k＝2和k＝3三種情況下，三種拓撲控制算法的干擾優化效果。當容錯度k取1、2、3三個不同值時，仿真結果都是一致的：OVFSS算法降低網絡干擾的能力都是優于其它兩種拓撲控制算法。這里只給出k＝3時（容錯能力度量值）三種拓撲控制算法的仿真結果。

Figure 3 Comparison of node interference among OVFSS，3D k－GG and 3D k－YG topology subgraph圖3 OVFSS、3D k－GG和3D k－YG生成的拓撲圖節點干擾比較

由圖3可知，OVFSS算法生成的拓撲圖的最大節點干擾和平均節點干擾值都是最小的，相對于原圖UBG來說，OVFSS算法生成的拓撲圖的點干擾值遠遠小于UBG圖中的點干擾值，也同樣小于其它三種拓撲圖的點干擾值。3D k－GG算法生成的拓撲圖的點干擾值要小于3D k－YG算法生成的拓撲圖中的點干擾值。3D k－YG算法生成的拓撲圖中的點干擾值相對于原圖UBG來說還是有一定程度的減少。而且隨著網絡中節點數的增加，原圖UBG和3D k－YG算法生成的拓撲圖的點干擾值會線性增長，而OVFSS算法生成的拓撲圖的點干擾值維持在一個較小的定值左右，并不會隨著節點數的增加而增大。

由圖4可知，隨著節點數的增加，3D k－GG算法與OVFSS算法都可以有效地調節節點的發射功率，使得網絡在保證k容錯的同時，最小化網絡中的干擾。OVFSS算法生成的拓撲圖的邊干擾值是最低的，遠低于其它三種算法生成的拓撲圖中的干擾值。而且隨著節點數的增加，這一結果更加明顯。

以上仿真結果表明，在三維空間網絡中OVFSS拓撲控制算法的干擾優化效果都是較好的。

下面對OVFSS算法、3D k－GG算法和3D k－YG算法在能耗優化方面進行比較。

Figure 4 Comparison of edge interference among OVFSS，3D k－GG and 3D k－YG topology subgraph圖4 OVFSS、3D k－GG和3D k－YG生成的拓撲圖邊干擾比較

實驗場景［8］為20×20×20的三維空間，節點的最大發射功率為9，節點數從50到175遞增，β值取2。實驗分別比較了干擾較弱（s＝0）時不同容錯度k＝1，k＝2和k＝3三種情況下，三種拓撲控制算法的能耗優化效果。當容錯度k取1、2、3三個不同值時，仿真結果都是一致的：OVFSS算法降低節點能耗的能力都是優于其它兩種拓撲控制算法。這里只給出k＝3時三種拓撲控制算法的仿真結果。

由圖5可知，在同樣大小的區域內，隨著網絡內部署的節點數的增加，網絡節點密集程度上升，由于采用多跳短距離通信代替長距離通信，節點可以使用更小的傳輸功率來發送信息給鄰居節點，再由鄰居節點進行轉發，3D k－GG、3D k－YG、OVFSS算法都能有效地調整節點傳輸功率，保證網絡在k連通，并且在節點數目相同時，OVFSS算法在減小能耗方面要比其他兩個拓撲控制算法效果好。

6 結束語

Figure 5 Comparison of node transmission power among OVFSS，3D k－GG and 3D k－YG topology subgraph圖5 OVFSS、3D k－GG和3D k－YG生成的拓撲圖節點傳輸功率比較

本文針對Ad Hoc網絡可能應用在通信環境發生變化的場景，提出了一種更加真實的三維場景下優化目標可變的、保證k連通的容錯拓撲控制算法，在干擾較強時，降低干擾并盡量節能；干擾較小時，重點考慮節能。并證明了該算法得到的通信子圖干擾最小，并保證k連通。真實應用場景通信環境復雜，優化目標側重點應該變化，需要綜合考慮干擾優化，根據剩余能耗選擇鏈路、網絡容錯性能、應用服務質量QoS（Quality of Service）保證等諸多問題，如何更加全面、合理地設置各部分影響因素對算法的影響需要進一步研究。

［1］ Wang Dong，Chen Wen－bin，Li Xiao－hong，et al.Distributed topology control algorithm for ad hoc networks using steered beam directional antennas［J］.Journal of Computer Research and Development，2010，47（3）：407－415.（in Chinese）

［2］ Chew L P.There is a planar graph almost as good as the complete graph［C］∥Proc of the 2nd Annual Symposium on Computational Geometry（SCG’86），1986：169－177.

［3］ Wang Y，Li X Y.Minimum power assignment in wireless ad hoc networks with spanner property［J］.Journal of Combinatorial Optimization，2006，11（1）：99－112.

［4］ Shpungin H，Segal M.Near optimal multi－criteria spanner constructions in wireless ad－hoc networks［C］∥Proc of IEEE INFOCOM’09，2009：163－171.

［5］ Rickenbach P V，Wattenhofer R，Zollinger A.Algorithmic models of interference in wireless ad hoc and sensor networks［J］.IEEE/ACM Transactions on Networking（TON），2009，17（1）：172－185.

［6］ Renato E N，Celso C R，Christophe D.Optimal solutions for fault－tolerant topology control in wireless ad hoc networks［J］.IEEE Transactions on Wireless Communications，2009，8（12）：5970－5981.

［7］ Li L，Lian L，Bin H.Algorithms for k－fault tolerant power assignments in wireless sensor networks［J］.Science China Information Sciences，2010，53（12）：2527－2537.

［8］ Indranil S，Lokesh K S，Subhas K G，et al.Distributed faulttolerant topology control in wireless multi－hop networks［J］.Wireless Networks，2010，16（6）：1511－1524.

［9］ Wang Y，Cao L，Teresa A，et al.Self－organizing fault－tolerant topology control in large－scale three－dimensional wireless networks［J］.ACM Transactions on Autonomous and Adaptive Systems（TAAS），2009，4（3）：1－21.

［10］ Rodoplu V，Meng T H.Minimum energy mobile wireless networks［J］.IEEE Journal on Selected Areas in Communications，1999，17（8）：1333－1344.

［11］ Cardieri P.Modeling interference in wireless ad hoc networks［J］.IEEE Communications Surveys ＆Tutorials，2010，12（4）：551－572.

［12］ Kruskal J B.On the shortest spanning subtree of a graph and the traveling salesman problem［C］//Proc of the American Mathematical Society，1956：48－50.

［13］ Wang D，Long W C，Li X H.Interference－aware fault－tolerant energy spanner in wireless ad hoc networks［J］.International Journal of Distributed Sensor Networks 2012，Article ID 235374，doi：10.1155/2012/235374.

附中文參考文獻：

［1］ 王東，陳文斌，李曉鴻，等.自組網中基于自適應波束天線的拓撲控制算法［J］.計算機研究與發展，2010，47（3）：407－415.