支持網(wǎng)絡(luò)編碼的認知無線自組網(wǎng)拓撲控制算法

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

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

1 引言

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

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

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

2 支持網(wǎng)絡(luò)編碼的無線自組網(wǎng)拓撲控制算法

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

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

圖1 2冗余網(wǎng)絡(luò)

2.1 初始拓撲構(gòu)建

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

針對無線自組網(wǎng)中的多播業(yè)務(wù)（假設(shè)都為單源多播業(yè)務(wù)），如圖2所示，設(shè)K=2，源節(jié)點為s，目的節(jié)點集為D，其余為中間節(jié)點集M。基于網(wǎng)絡(luò)編碼的最短路徑算法步驟如下。

圖2 基于網(wǎng)絡(luò)編碼的最短路徑算法

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

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

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

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

Step 3如果K≤m，轉(zhuǎn)到Step4；否則，轉(zhuǎn)到Step5。

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

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

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

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

2.2 拓撲優(yōu)化

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

圖3 拓撲優(yōu)化

1) 構(gòu)建臨時拓撲

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

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

2) 探測臨時拓撲圖

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

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

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

2.3 拓撲恢復

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

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

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

1) 收集局部網(wǎng)絡(luò)拓撲信息

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

2) 恢復鏈路組的連通性

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

3) 恢復局部網(wǎng)絡(luò)連通性

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

2.4 算法支持網(wǎng)絡(luò)編碼的實例

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

3 仿真分析

3.1 有效性

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

圖4 基于關(guān)鍵點失效的拓撲恢復算法

表1 仿真參數(shù)

定義5(網(wǎng)絡(luò)吞吐量)：指一組特定數(shù)據(jù)在特定時間段經(jīng)過特定路徑所傳輸?shù)男畔⒘康膶嶋H測量值。

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

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

圖5 分組投遞率隨信宿節(jié)點數(shù)變化的對比

圖6 網(wǎng)絡(luò)吞吐量隨信宿節(jié)點數(shù)變化的對比

圖7 節(jié)點平均能耗隨信宿節(jié)點數(shù)變化的對比

3.2 抗毀性

仿真環(huán)境與探測有效性時一致，信宿節(jié)點數(shù)設(shè)為10個。對比在TCBNC拓撲控制前后，網(wǎng)絡(luò)性能指標隨失效關(guān)鍵點數(shù)增加時的變化情況。

圖8 分組投遞率隨失效關(guān)鍵點數(shù)變化的對比

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

圖9 網(wǎng)絡(luò)吞吐量隨失效關(guān)鍵點數(shù)變化的對比

4 復雜度分析

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

圖10 初始網(wǎng)絡(luò)拓撲圖

圖11 最短路網(wǎng)絡(luò)拓撲圖

5 結(jié)束語

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

[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] 胡金秀.多播網(wǎng)絡(luò)編碼算法研究[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.