支持網絡編碼的認知無線自組網拓撲控制算法

劉軍，孫茜，王英梅，葉寧，沙明博

（1.東北大學 信息科學與工程學院，遼寧 沈陽 110819；2.北方交大計算所，北京 100029；3.奧維通信股份有限公司，遼寧 沈陽110179）

1 引言

Ad hoc網絡[1]是由一組具有無線收發裝置的移動終端組成的多跳臨時性自治系統。該網絡具有無中心和自組織性、節點功能不同、傳輸帶寬受限、拓撲動態變化等特點。近年來，隨著認知網絡[2,3]的迅速發展，很多研究者將網絡認知技術融入無線自組網中，使其可以根據條件變化和發生的事件（如端到端的業務量）按照推理和先驗知識進行自適應，從而實現對拓撲結構的自管理、自優化、自監控、自修理、自保護和自治愈等。

隨著無線通信技術的日益發展，認知無線自組網中的業務逐漸增多，有限的帶寬成為限制其通信的主要因素。Ahlswede于2000年提出了網絡編碼技術[4]，其核心思想是節點將來自不同鏈路的數據分組進行編碼組合，在實現路由功能的同時實現編碼功能。網絡編碼技術[5,6]可以提高網絡吞吐量，增加多播容量，節省節點能耗，增加網絡安全性。因此，網絡編碼技術可以解決網絡中帶寬受限的問題，提高無線資源復用率。

由于網絡編碼是一種新興的技術，目前絕大多數拓撲控制算法[7,8]都不能支持網絡編碼的應用。直到2007年，Chi等人針對有線網絡提出一種支持網絡編碼的多播網絡拓撲構建方案[9]。論文中將該問題作為非線性規劃問題，證明其是NP問題，提出了2個啟發式算法LDE(link deletion and exchange)和LAE(link addition and exchange)。在2011年，Li在其基礎上，將該問題制定為特殊的K連通問題，利用遺傳算法提出一種支持網絡編碼的拓撲設計方案[10]，但是，其優化目標較為簡單，需要更加深入的研究。因此，構建支持網絡編碼的拓撲控制算法仍然具有廣闊的研究空間。

2 支持網絡編碼的無線自組網拓撲控制算法

網絡編碼能夠順利進行的前提條件之一是網絡拓撲結構存在冗余性，Ahlswede所用的著名蝶形網絡很好地說明了這個問題。針對每個多播業務，若源節點到每個目的節點都存在K條邊分離路徑，那么采用網絡編碼技術可以實現多播傳輸的極限傳輸速率。如圖1所示的2冗余網絡（源節點到每個目的節點都存在2條邊分離路徑），s是源節點，t1、t2、t3是目的節點，a和b是要傳輸的數據分組，鏈路具有單位帶寬。若源節點s對數據分組a和b進行網絡編碼后再傳輸，在鏈路s-u2、u2-t1、u2-t3上可以實現傳輸速率2bit/s。

基于以上思想，為采用網絡編碼技術解決無線自組網中帶寬受限的問題，提出了支持網絡編碼的拓撲控制算法(TCBNC, topology control algorithm backing for network coding)。算法主要分為3個階段：初始拓撲構建、拓撲優化和拓撲恢復。

圖1 2冗余網絡

2.1 初始拓撲構建

無線自組網中的通信類型多種多樣，在拓撲構建過程中，需要在面向業務的框架下設計滿足多業務需求的網絡拓撲，適應其多元化的特點。針對網絡中的單播業務，利用最短路徑算法選擇源節點到目的節點的最短路徑，構建網絡拓撲；針對網絡中的多播業務，利用基于網絡編碼的最短路徑算法選擇源節點到每個目的節點的K（K值不同，最大傳輸速率不同）條邊分離路徑，構建K冗余網絡。

針對無線自組網中的多播業務（假設都為單源多播業務），如圖2所示，設K=2，源節點為s，目的節點集為D，其余為中間節點集M?；诰W絡編碼的最短路徑算法步驟如下。

圖2 基于網絡編碼的最短路徑算法

Step1在初始拓撲圖G（如圖2(a)）中，使用最短路徑算法搜索源節點s到每個中間節點的最短路徑，得到最短路拓撲圖G′。如圖2(b)所示，源節點到中間節點的最短路徑分別為sm1、sm2、sm3、sm2m4、sm5。目的節點的輸入鏈路為m1d1、m3d1、m4d1、m3d2、m4d2、m5d2、m4d3、m5d3。

定義1（最短路拓撲圖）：在單源多播網絡初始拓撲圖G中，s為源節點，D為目的節點集，采用最短路徑算法搜索源節點到每個中間節點的最短路徑，再加上G中所有目的節點的輸入鏈路構成的拓撲為最短路拓撲圖G′。

Step 2計算最短路拓撲圖G′中源節點s到每個目的節點di（di∈D，i=1,2,···,|D|）的邊分離路徑數及最小值m。在圖2(b)中，計算得m=2。

定義2（邊分離路徑）：由目的節點的輸入鏈路及輸入鏈路另一端點到源節點的最短路徑構成的彼此之間沒有重合鏈路的路徑。在圖2(b)中，對于目的節點d1，邊分離路徑為sm1d1、sm3d1、sm2m4d1。

Step 3如果K≤m，轉到Step4；否則，轉到Step5。

Step 4在最短路拓撲圖G′中，對每個目的節點重復采用最短路算法，搜索從源節點s到每個目的節點di的K條最短邊分離路徑，構建拓撲圖G0，如圖2(c)所示，可以找到源節點到每個目的節點的2條邊分離路徑，算法結束。

Step 5在最短路拓撲圖G′中，對每個目的節點重復采用最短路算法，搜索從源節點s到每個目的節點di的m條最短邊分離路徑。

Step 6對于每個目的節點di，將Step5中搜索到的m條最短邊分離路徑中的鏈路在初始拓撲圖G中刪除得新初始拓撲圖G′′，在G′′中重復使用以上算法，搜索源節點s到每個目的節點di的K-m條最短邊分離路徑，算法結束。

綜上所述，利用不同的算法可以為不同的業務選擇合適的路徑或路徑簇，構建初始拓撲圖G0。不同路徑或路徑簇之間可能存在重合鏈路，增加了網絡編碼的應用機會。如果在重合鏈路的端節點采用網絡編碼技術，可以提高網絡吞吐量。注意，算法中的“路徑”可能代表時延、帶寬、能耗等。

2.2 拓撲優化

在初始拓撲構建階段，構建的拓撲結構具有很大的冗余性。因此，需要在保證網絡編碼應用的前提下，對拓撲結構進行優化，節省網絡能量消耗。如圖3(a)所示的拓撲圖G0，K=2，網絡中包括多播業務Q1（源節點s1，目的節點d11、d12、d13，邊分離路徑簇為s1m1d11、s1m3d11、s1m3d12、s1m2m4d12、s1m2m4d13、s1s3d21d13）、Q2（源節點s2，目的節點d21、d22，邊分離路徑簇為s2d21、s2s3d21、s2m2m4d22、s2s3d22）和單播業務 Q3（源節點s3、目的節點d3、最短路徑為s3d3）。拓撲優化階段的步驟如下。

圖3 拓撲優化

1) 構建臨時拓撲

在拓撲圖G0中，選擇效率指標最大的鏈路lmax。從 G0中刪除鏈路lmax，獲得臨時拓撲圖 GT，如圖3(b)所示。

定義3 (效率指標)：鏈路上單位流量的能量消耗。

2) 探測臨時拓撲圖

①探測臨時拓撲圖GT中的多播業務是否滿足K冗余。若滿足，轉到②；否則，說明鏈路lmax不能被刪除，在剩余網絡拓撲（不包括鏈路lmax）中重復1)。從圖3(b)可以看出，GT滿足2冗余條件。

②為鏈路lmax上的業務重新選擇合適的路徑，判斷網絡總能耗是否減小。若減小，將臨時拓撲圖 GT作為新初始拓撲圖 G0；否則，說明鏈路lmax不能被刪除，在剩余網絡拓撲中重復1）。在圖3中，鏈路lmax被刪除后，其上的單播業務Q3可以選擇新的路徑s3d21d3，假設計算后，網絡的總能耗減小，因此，將臨時拓撲圖GT作為新初始拓撲圖G0。

上面的過程重復進行，直到拓撲圖 G0中不存在能被刪除的鏈路，算法結束。

2.3 拓撲恢復

Ad hoc網絡中存在一些拓撲關鍵點，一旦網絡認知到某個關鍵點發生故障或受到安全威脅，與關鍵點相連的鏈路會失效，網絡很容易被分割成不連通的子網。為了保證網絡可靠、安全運行，提出基于關鍵點失效的拓撲恢復算法，主要思想是采用與失效鏈路不在同一路徑簇中且開銷最小的鏈路恢復網絡的連通性，以保證源節點到每個目的節點間的路徑是邊分離的，繼續支持網絡編碼的應用。

定義4(關鍵點)：網絡中某個節點失效可能導致網絡被分割成多個部分，這樣的節點稱為網絡拓撲關鍵點，如圖4(a)所示，節點a是關鍵點。

以圖 4為例說明基于關鍵點失效的拓撲恢復算法。

1) 收集局部網絡拓撲信息

收集關鍵點a周圍的兩跳網絡拓撲信息，將屬于同一路徑簇中的鏈路劃為一組，得到3個不同的鏈路組L1、L2、L3，如圖4(a)所示。

2) 恢復鏈路組的連通性

隨機選取鏈路組L1，當關鍵點a失效時，路徑b1ab6的連通性遭到破壞，將鏈路組L1中的鏈路開銷置為無窮大，利用最短路徑算法搜索節點b1到b6的新路徑b1b4b3b6，添加到局部網絡中，如圖 4(b)所示。然后，探測此時L2中路徑連通性是否遭到破壞，從圖4(b)中看出，可以找到新路徑b4b1b2b5，連通性不再受影響；否則，采用最短路徑算法恢復連通性。對于剩余鏈路組重復使用以上算法。注意，鏈路組L3的連通性暫時不能恢復。

3) 恢復局部網絡連通性

計算此時關鍵點a失效時局部網絡中簇的個數N。若N不為1，添加能使簇個數減小的最小開銷鏈路li（i=1，2，3，···），直到N=1，如圖 4(c)中鏈路l1；否則，算法結束。網絡進行拓撲恢復后如圖4(c)所示。

2.4 算法支持網絡編碼的實例

以拓撲圖3（b）中多播業務Q1為例，說明網絡編碼在拓撲結構中的具體體現。設源節點向目的節點發送信息a、b，目的節點d11的邊分離路徑簇為s1m1d11、s1m3d11，目的節點d12的邊分離路徑簇為s1m3d12、s1m2m4d12，這 2個路徑簇構成了網絡編碼的典型應用環境——蝶形網絡。在源節點處對a、b進行網絡編碼，將編碼后的信息在重合鏈路s1m3、m3d11、m3d12上傳輸，在其他鏈路上傳輸a或b，可保證目的節點d11、d12成功解碼出信息a、b。同樣方法，可保證目的節點d13成功收到a、b。不論編碼方法如何，構建的拓撲結構都能夠支持網絡編碼的應用，并確保成功解碼。

3 仿真分析

3.1 有效性

采用NS2網絡模擬軟件進行測試，設置網絡中同時存在單播和多播業務，對比在TCBNC和基于多播樹的拓撲控制算法(TCBMT，topology control algorithm based on multicast tree)的控制下，網絡分組投遞率、吞吐量、節點平均能耗隨信宿節點數增加時的變化情況，仿真參數如表1所示。

圖4 基于關鍵點失效的拓撲恢復算法

表1 仿真參數

定義5(網絡吞吐量)：指一組特定數據在特定時間段經過特定路徑所傳輸的信息量的實際測量值。

定義6(節點平均能耗)：指網絡中每個節點在運行過程中所消耗的能量的平均值。在計算過程中，考慮了網絡運行過程中影響節點能量的所有因素，其計算公式為

從圖5～圖7可以看出，TCBNC能夠提高網絡的分組投遞率和網絡吞吐量，降低網絡的節點平均能耗。這是因為TCBNC能夠構建出支持網絡編碼的拓撲結構，增加了節點進行網絡編碼的機會，因此提高了網絡分組投遞率和吞吐量，節省了節點平均能耗。隨著網絡中信宿節點數的增加，TCBNC控制的網絡中更多的節點參與網絡編碼，增大編碼機會的同時提高了解碼成功概率，大量數據分組能夠成功到達目的節點，網絡的分組投遞率幾乎不變，吞吐量逐漸增大，節點平均能耗逐漸增大；而TCBMT控制的網絡中由于數據分組的逐漸增多，網絡阻塞、數據分組丟失和重傳現象十分嚴重，網絡性能逐漸下降。

圖5 分組投遞率隨信宿節點數變化的對比

圖6 網絡吞吐量隨信宿節點數變化的對比

圖7 節點平均能耗隨信宿節點數變化的對比

3.2 抗毀性

仿真環境與探測有效性時一致，信宿節點數設為10個。對比在TCBNC拓撲控制前后，網絡性能指標隨失效關鍵點數增加時的變化情況。

圖8 分組投遞率隨失效關鍵點數變化的對比

從圖8和圖9可以看出，隨著網絡中失效關鍵點數的增加，支持網絡編碼的拓撲控制算法能夠顯著提高網絡的分組投遞率和吞吐量，改善網絡的性能。一方面，TCBNC通過建立新鏈路，保證了網絡的連通性，數據分組能夠順利到達目的節點；另一方面，修復后的網絡拓撲結構能夠繼續支持網絡編碼的應用，減少了數據分組的傳輸次數，提高網絡吞吐量。因此，TCBNC使網絡性能得到了有效的恢復，增強了網絡的抗毀性。

圖9 網絡吞吐量隨失效關鍵點數變化的對比

4 復雜度分析

TCBNC的復雜度小于對比TCBMT的復雜度，主要體現在多播業務的拓撲構建過程中利用了最短路網絡。圖 10所示為初始網絡拓撲圖，源節點為s，目的節點為d，K=2，利用TCBMT搜索兩條最短路徑需要的計算次數為 2×(15+14+···+2)= 238；利用 TCBNC構建最短路網絡的計算次數為14+13+···+2=104，如圖 11 所示，在其基礎上搜索一條最短路徑的計算次數為 15，總計算次數為104+2×15=134，節約了 43.7%的計算量。并且，隨著目的節點數、K值的增加，算法具有更低的復雜度。

圖10 初始網絡拓撲圖

圖11 最短路網絡拓撲圖

5 結束語

本文提出一種支持網絡編碼的認知無線自組網拓撲控制算法 TCBNC，針對不同的業務類型采用不同算法構建支持網絡編碼的初始拓撲圖，然后通過逐個刪除冗余鏈路進行拓撲優化，最后提出解決關鍵點失效問題的拓撲恢復算法。算法支持網絡編碼的應用，增強了通信的有效性和抗毀性。另外，算法復雜度不大，在節點移動或信道環境變化時仍能適用。在未來的工作中，將考慮鏈路失效的情況，重構支持網絡編碼的拓撲。

[1] DE MORAIS CORDEIRO C, GOSSAIN H, AGRAWAL D P.Multicast over wireless mobile ad hoc network： present and future directions[J].IEEE Communications Society, 2003, 17(1)： 52-59.

[2] RABBACHIN A, QUEK T Q S, HYUNDONG S.Cognitive network interference[J].IEEE Journal on Communications, 2011, 29(2)：480-493.

[3] WANG Z D, WANG H Q, FENG G S.Cognitive networks and its layered cognitive architecture[A].2010 Fifth International Conference on Internet Computing for Science and Engineering(ICICSE)[C].Heilongjiang, China, 2012.145-148.

[4] LI B C, NIU D.Random network coding in peer-to-peer petworks：from theory to practice[J].Proceedings of the IEEE, 2010, 99(3)：513-523.

[5] AHN M H, KIM Y Y.Network coding-based multicast scheduling for throughput enhancement in wireless ad hoc network[A].2011 International Conference on Information Networking[C].Barcelona, Spain,2011.188-193.

[6] 胡金秀.多播網絡編碼算法研究[D].西安： 西安電子科技大學,2010.HU J X.Study on Multicast Network Coding Algorithm[D].Xian： Xidian University, 2010.

[7] ZHANG T, YANG K, CHEN H H.Topology control for service-oriented wireless mesh networks[J].IEEE Wireless Communications, 2009, 16(4)： 64-71.

[8] YADU K K, KAKDE O G.Optimization based topology control for wireless ad hoc networks to meet QoS requirements[A].2010 29th IEEE Symposium on Reliable Distributed System[C].New Delhi, India, 2010.30-36.

[9] CHI K K, JIANG X H, HORIGUCHI S.Topology design of network-noding-based multicast networks[J].IEEE Transactions on Parallel and Distributed Systems, 2008, 19(5)： 627-640.

[10] LI J K, PAN Y.Network coding driented topology design based on parallel genetic algorithm[A].2011 Fourth International Joint Conference on Computational Sciences and Optimization[C].Yunnan, China,2011.838-841.