基于網絡編碼的無線多跳網絡壽命優化模型研究

李　明　王　睿　馬　睿　汪新建　童　玲

(中國人民解放軍成都軍區總醫院網絡管理中心　四川 成都 610083)

?

基于網絡編碼的無線多跳網絡壽命優化模型研究

李明王睿馬睿汪新建童玲

(中國人民解放軍成都軍區總醫院網絡管理中心四川 成都 610083)

摘要針對無線多跳網絡的壽命優化問題，通過將無網絡編碼、雙向網絡編碼和偵聽網絡編碼的壽命優化問題轉化為線性約束規劃問題，提出一種基于網絡編碼的無線多跳網絡壽命優化模型。在該模型中，基于功率控制模型、數據流個數、業務需求分布和每個節點初始能量的隨機拓撲模型，首先對這三種不同情形下的網絡壽命優化問題進行建模。然后使用內點法對這些問題進行求解，最后評估網絡壽命。通過對多種情況下網絡編碼對網絡壽命的影響進行仿真，驗證了模型的有效性。仿真結果表明，在弱功控情況下網絡編碼可以取得較好的網絡壽命增益，且該增益隨數據流個數的增加而增加，相對于偵聽網絡編碼方法，雙向網絡編碼方法在取得相近性能的同時，具有更低的計算開銷。

關鍵詞壽命優化無線多跳網絡網絡編碼線性規劃隨機拓撲模型

ON LIFETIME OPTIMISATION MODEL FOR WIRELESS MULTI-HOP NETWORKS BASED ON NETWORK CODING

Li MingWang RuiMa RuiWang XinjianTong Ling

(Department of Network Management Center,Chengdu Military General Hospital,Chengdu 610083,Sichuan,China)

AbstractFor the problem of wireless multi-hop networks lifetime optimisation, we proposed a network coding-based wireless multi-hop networks lifetime optimisation model by converting the problem of lifetime optimisation for networkless coding, two-way network coding and interception network coding to linear-restriction programming problem. In this model, based on the power control model, the number of data flows, the traffic demand distributions and the stochastic topology model of initial energy of each node, we first modelled the network lifetime optimisation problems under these three different scenarios, then solved them via the interior-point method, and finally evaluated the networks lifetime. To verify the validity of the model, we simulated the impact of network coding on network lifetime under various network environments. Simulation results showed that with weak power control the network coding could achieve better networks lifetime gain, and which increased with the increase of the number of data flow, and that the two-way network coding method, relative to interception network coding, performed close to it but had lower computation overhead.

KeywordsLifetime optimisationWireless multi-hop networksNetwork codingLinear programmingStochastic topology model

0引言

在能量受限的無線多跳網絡中，更換節點電池或給節點電池充電通常是不方便或是不可能的。因此，最小化所有節點尤其是瓶頸節點的能量消耗對延長網絡壽命非常重要。由于整個網絡的能量最小化可能導致某些瓶頸節點的過度使用和網絡的斷開，所以研究網絡壽命比研究能源消耗更有意義。網絡編碼方法可有效改善網絡的吞吐量性能[1,2]和功率的消耗[3-5]。Ahlswede首先提出了網絡編碼，并證明多播的速率域，即從源點到匯點的最小割/最大流，可以通過線性網絡編碼來獲得[6]。將網絡編碼運用到無線多跳網絡中，亦會給網絡的優化帶來新的機遇與挑戰。網絡編碼的研究對象主要包括兩類：最優的單播網絡中的網絡編碼，即會話內網絡編碼；最優的廣播網絡編碼，即會話間的網絡編碼。對會話內網絡編碼已經有了深入全面的了解，并可利用線性網絡編碼對其進行實現[7,8]。針對網絡優化問題，相關文獻提出了在無線和有線網絡中基于會話內網絡編碼多播的容量區域，采用動態背壓算法和全分布交叉層算法來實現多播在分配方式上吞吐量的優化[9,10]。基于網絡編碼的最低代價多播可以在多項式時間內或者采用雙分布式子梯度法加以實現，其等同于基于線性邊緣定價的最低成本[3,4]。針對使用會話間網絡編碼的網絡優化問題，相關工作已開展。針對預定路由，提出了調度的聯合優化和網絡編碼以及背壓優化策略并對之加以分析[1,11]。針對聯合路由和網絡編碼采用線性規劃法進行理論分析。結果表明，編碼和干擾感知路由相較于編碼無關路由可以產生更高的性能增益[2]。相關文獻針對成對對話間網絡編碼的網絡應用優化問題進行了建模研究[12]。

然而，到目前為止，很少有研究基于網絡編碼的無線多跳網絡的壽命最大化問題。對于沒有網絡編碼情形下的壽命優化問題，可通過分布式子梯度迭代法[13]或啟發式流量擴張路由法[14]來加以解決。針對網絡編碼情形下的壽命優化問題，相關文獻考慮了在某些具體情況下，應用網絡編碼的壽命延長問題[15]并通過簡便的拓撲法，對使用網絡編碼的多播壽命最大化問題進行了建模分析和評估[16]。另外，相關文獻對使用單跳網絡編碼的壽命最大化問題進行了建模分析和解析[17]。但是，針對對話間網絡編碼對網絡壽命的影響仍未得出確切的結論。

因此，本文主要研究使用會話間網絡編碼的無線多跳網絡的壽命最大化問題，分析網絡壽命隨會話間網絡編碼的延長程度并研究影響改善率的因子。本文考慮兩種編碼方法，即雙向網絡編碼和偵聽網絡編碼，并分別評估它們的性能、復雜度和開銷。

1基本原理與模型

1.1網絡模型

通常將無線多跳網絡建模為一個有向圖G={V,E}，其中V是節點集合，E是鏈路集合。這里假設鏈路是對稱的，即如果鏈路(i,j)∈E，則(j,i)∈E。使用rij指代鏈路(i,j)的速率。在本文中，分別用c、C、sc和dc代表從特定源節點和目的節點的數據流、數據流集合、源節點和目的節點。

目前傳輸功率控制是一種有效降低功率消耗和空間干擾的技術。此前對網絡壽命的研究通常假設完全功率控制，而實際系統通常只能支持有限功率控制。故本文考慮兩種極端情形：1) 未采用傳輸功率調整的協議模型；2) 采用完全功率控制的物理模型。

給定一種用于資源分享和調度的干擾模型，例如基本或者K跳干擾模型，網絡G的可達速率域定義為Co(r)，它可用一個多維多面體來表示。

1.2網絡編碼

本文考慮單跳網絡中使用的線性異或網絡編碼方式，該編碼方式與c=a⊕b類似。這里，a和b為輸入分組，c為異或之后的輸出分組。基于兩符號(分組)的網絡編碼占COPE的50%以上，占COPR的99%以上[12]。另外，對實際系統的研究也發現多于兩個符號的網絡編碼運算會使優化過程極其復雜。因此，本文對網絡編碼的分析將在使用線性異或網絡編碼的單跳成對網絡中進行。對于超過兩個符號的網絡編碼，可以通過伺機方式，如在COPE和COPR中來實現。

下面的引理給出了單跳成對網絡編碼正常工作的要求。

引理1在單跳網絡編碼中，對于節點k，若想從節點i傳輸的編碼分組Pc=Px⊕P解碼出分組Px，則該節點需滿足以下兩個條件：1) 節點k從節點i接收到分組Pc；2) 節點k獲得了未編碼分組P。

考慮兩種節點k獲得未編碼分組P的機會：① 通過鏈路(k,i)將P傳輸到節點i，如圖1(a)中所示的節點k處的分組P2；② 節點k正確地從其他鏈路偵聽到分組P，如圖1(b)中所示的由節點k從鏈路(m,k)偵聽到的分組P2。根據節點獲得未編碼分組的這兩種方式，定義單跳成對網絡中的兩種網絡編碼：① 雙向網絡編碼方式，該方式僅包含機會1)中的分組；② 偵聽網絡編碼方式，該方式同時包含機會1)和機會2)中的分組。

圖1　單跳網絡編碼

由于單跳網絡編碼同時涉及到前跳節點和后跳節點，為了描述的簡便，本文定義了一種雙跳鏈路。

定義1(雙跳鏈路)對于節點i，從節點j到節點k經過節點i的鏈路稱為節點i處的雙跳鏈路，記為(j,i,k),j≠k。

需要注意的是，對于從源節點開始的傳輸，有j=i，而對于目的節點的接收，有i=k。

從上面的定義和描述可以看出，單跳網絡編碼依賴于鄰居節點的相對位置。例如，在圖1(b)中，雙向鏈路(j,i,k)和(m,i,n)可以同時進行編碼，這是因為節點k和n可以分別偵聽到節點m和j的數據。而雙跳網絡(j,i,k)和(n,i,m)就不能同時編碼。由此可以得到可同時進行網絡編碼的雙向鏈路在幾何上的結構定義。

定義2(網絡編碼結構)網絡編碼結構指的是在幾何上能夠同時編碼的雙向鏈路的有序集合。

使用上述定義和簡記法，可以表述下述引理，以確定一種網絡編碼情況是雙向網絡編碼還是偵聽網絡編碼。

引理2Si是雙向網絡編碼結構,當且僅當p(Si)=n(Si)，而Si是偵聽網絡編碼結構,當且僅當p(Si)≠n(Si)。

1.3網絡壽命

網絡壽命指的是網絡運行良好，尤其是滿足網絡所有需求的持續時間。以前的研究對不同應用場景下的網絡壽命提出了多種定義，例如所有節點的最小壽命、壽命向量等。為了簡化分析，本文采用了第一種定義，并將其擴展，以使其適合文中分析網絡編碼的情況。

(1)

其中，第一項為節點i處的傳輸數據流c的功率消耗，第二項是從所有鄰節點j∈V接收的數據流c的功率消耗，第三項是偵聽的接收功率消耗。需要注意的是，對于一個網絡編碼結構Sj，節點i處的偵聽條件為i∈n(Sj)，而i?p(Sj)。

節點i處的壽命就可表示為：

(2)

其中，網絡壽命由節點i的能量Ei和節點i處理所有分組所消耗的功率決定。由此得到整個網絡的壽命：

(3)

2基于網絡編碼的無線多跳網絡壽命優化模型

對無網絡編碼情形、雙向網絡編碼情形和偵聽網絡編碼情形下的網絡壽命優化問題進行模型化描述。其中，無網絡編碼情形下的優化問題是另外兩種情形的基準。本文提出了一種新的公式化描述方法，該方法從節點和本地數據流的角度對優化問題進行描述，并具有低復雜度。

2.1無網絡編碼情形

無網絡編碼情形下，優化問題的約束與流量守恒法則、總能量限制、每條鏈路的可達速率域以及整個網絡有關。這種情形下，壽命優化問題可表述為：

maxT

(4)

(5)

(6)

(rij)∈Co(r)

(7)

(8)

其中，xc為數據流c的流量需求。

式(5)中的約束是能量約束，它說明了節點i在壽命T內的能量消耗不大于其初始能量Ei。式(6)和式(7)給出了速率約束，兩式解釋了鏈路(i,j)的總速率小于調度速率rij以及可達速率域Co(r)內的所有速率。

當鏈路速率足夠大以使所有鏈路都能同時滿足速率需求時，網絡壽命就不會受干擾模型和調度算法的影響。由于對于流量需求相對較小的能量受限的無線網路通常滿足這個條件，因此如式(6)和式(7)所示的速率約束可以忽略不計。優化問題可簡化為：

maxT

(9)

(10)

2.2雙向網絡編碼情形

maxT

(11)

(12)

(13)

其中，網絡編碼場景Fi集合僅包含雙向網絡編碼和未編碼傳輸。為了分析和研究的方便，這里假設它們之間并無差別。式(11)中的約束為流量守恒法則。式(12)中的約束是雙向網絡編碼的編碼和解碼要求，它表明在滿足(j,i,k)=Si(1)的網絡編碼結構Si上，數據流c的總傳輸速率小于該數據流從j到i的總輸入速率。能量約束由式(13)給出。

2.3偵聽網絡編碼情形

除了雙向網絡編碼中的約束，偵聽網絡編碼還需對前跳節點提出要求。為了正確解碼使用偵聽的分組，未編碼數據的偵聽速率應當大于總編碼速率。故該情形下的壽命最優化問題可表述為：

maxT

(14)

(15)

(16)

(17)

式(14)給出了流量守恒法則。與式(12)相同，式 (15)中的約束與編碼要求有關，即在滿足(j,i,k)=Si(1)，?k的網絡編碼結構Si上，數據流c的總傳輸速率小于來自j節點的總輸入速率。式(16)描述了使用偵聽的網絡編碼的解碼要求。所有編碼結構{Si}，包括(j,i,k)和(j′,i,k′),k≠j′的和速率應該小于從h到i，經過j′并由j偵聽的未編碼分組的速率。式(17)給出了能量約束。

2.4動態路由算法優化

在有網絡編碼場景下，為了優化網絡的壽命，使用動態路由算法對網絡的拓撲進行優化，進而可以使節點傳輸數據所需的路由更短，從而優化了網絡的壽命。

在動態路由算法中，節點i的周期消耗可表示為：

(18)

其中，Ni為節點i的鄰居節點集合，xij為節點i向節點j發送的信息數量，rij,tij分別為收發信息的能量損失系數，從而得到節點i的壽命：

(19)

其中bi為節點i的剩余能量。

從而網絡壽命可定義為：

(20)

其中，(0,i)∈E表示鏈路(0,i)為網絡中從原點到節點i的一條鏈路。

應用線性規劃最大最小網絡中的節點壽命：

?i∈N?j∈Ni

(21)

動態路由算法描述如下：

1) 初始化：獲取網絡的拓撲信息，k=1；

2) 執行式(21)的線性規劃過程，獲取節點的路由信息；

3) 當網絡中有節點因能量耗盡而失效時，更新網絡拓撲，如果存在基站的一跳節點，則轉2)，k=k+1；

3仿真實驗與分析

可采用性能評估的集中式解法[2]、對偶子梯度方法[3,13]和啟發式流量擴張路由法[14,19]來研究性能的評估，這里采用第一種方法。針對不同的能量分布的配置、業務需求、數據流個數和功率控制模型開展網絡壽命和計算開銷方面的評估工作。

3.1參數設置

為了深入分析網絡編碼對壽命的影響，使用簡單功率消耗模型。假設所有節點的物理特性和電氣特性都是相同的且信道衰落為參數α=4的指數平坦衰落，則將一個比特從節點i傳輸到節點j的能量消耗僅依賴于節點之間的距離和收發器的功率消耗。發送和接收的功率消耗可寫為：

(22)

(23)

3.2網絡壽命和性能仿真

該部分將評估一個基于多約束編碼的無線多跳網絡壽命性能。在80 m×80 m的正方形區域內隨機放置20個節點，且節點的平均度數為2.8。假設每個節點的初始能量服從均值為P的指數分布。每個節點產生16個數據流，且源節點從20個節點中隨機選擇。假定所有的數據流都具有合適的路徑，即每個數據流的源節點和匯聚節點都是相連的。

為了評估協議模型和物理模型下網絡壽命和計算開銷的性能。所有仿真都運行50次且性能指標的均值和方差都歸一到無網絡編碼情形下的對應值。

1) 平均壽命:設P=5并假設所有流量的需求為1 kbps，雙向網絡編碼和偵聽網絡編碼對不同數據流個數的歸一化結果如 圖 2所示。由圖可知：(1) 網絡壽命隨數據流個數的增加而增加，這是因為更多的數據流個數會產生更多的編碼機會。由于傳輸功率最高的鏈路決定著傳輸功率消耗，使用完全功率控制的物理模型所能節省的能量有限，故傳輸功率協議模型下的壽命增益遠高于物理模型下的壽命增益；(2) 雙向網絡編碼和偵聽網絡編碼下的壽命之間的差距并不顯著，甚至可以忽略。

圖2　在物理和功率協議模型下，使用雙向和偵聽網絡編碼的歸一化壽命隨不同數據流個數的變化情況

2) 計算開銷:使用迭代次數來評估優化問題的計算開銷，仿真結果如圖3所示。由圖可知：(1) 兩種功率控制模型下，迭代次數隨著數據流個數的增加而增加；(2) 物理模型下的迭代次數比協議模型下的迭代次數高；(3) 使用偵聽網絡編碼的迭代次數要高于使用雙向網絡編碼的迭代次數。

圖3　迭代次數隨數據流個數的變化情況

3) 初始能量的影響:雙向網絡編碼和偵聽網絡編碼歸一化壽命的編碼機制涉及兩種不同的初始能量配置，即P=1和P=5。不同初始能量配置下的兩類模型的網絡壽命如圖4所示。圖中，物理功率控制模型和協議功率控制模型分別用Phy，Pro表示，雙向網絡編碼方式和偵聽網絡編碼方式分別用2W和OH表示。可以發現壽命均隨著數據流個數的增加而增加，但壽命和初始能量之間并不存在簡單的對應關系。

圖4　不同初始能量，網絡編碼機制和功率控制模型下的網絡壽命

4) 業務非對稱性的影響: 假設所有數據流的業務需求都是相等的，而實際網絡中這種對稱網絡不存在，故需研究業務非對稱性對隨機拓撲網絡壽命的影響。設定P=5，假設每個數據流的業務需求服從均值為F的指數分布。不同功率控制模型、網絡編碼機制和均值情況下的壽命仿真結果如圖5所示。由圖可知：雙向和偵聽網絡編碼機制的性能相近，與流量需求的平均值無關。

圖5　不同業務需求，網絡編碼機制和功率控制模型下的壽命

通過以上仿真結果，可以發現：(1) 在弱功控情況下，網絡編碼可以取得較好的壽命增益，且該增益隨數據流個數增加而增加；(2) 壽命增益和網絡編碼的計算開銷都均隨數據流個數的增加而增加；(3) 業務需求分布和節點初始能量對壽命性能的影響可忽略不計；(4) 偵聽網絡編碼對壽命的優化表現與雙向網絡編碼相近，但其計算開銷更高；(5) 在有網絡編碼場景下，使用動態路由算法，可進一步提高網絡的壽命。因此，在實際系統中，使用會話間的網絡編碼并配合動態路由算法，可以使網絡壽命得到優化；在計算開銷上，使用雙向網絡編碼更具適應性。另外，上述網絡壽命最優化建模和仿真試驗結果為分析無線多跳網絡參數對網絡壽命性能的影響提供了方法和思路。

4結語

本文主要研究基于網絡編碼的無線多跳網絡的壽命最大化問題。針對無網絡編碼、雙向網絡編碼和偵聽網絡編碼三種情形，對無線多跳網絡壽命的最優化問題進行了建模，并將壽命最大化問題轉化為線性規劃問題。然后通過研究數據流個數、功率控制模型、節點初始能量以及業務非對稱性，針對三種情形下的網絡壽命和計算開銷進行了對比分析。仿真結果表明，使用網絡壽命性能增益和計算開銷均隨數據流個數的增加而增加，業務需求分布和節點初始能量對壽命性能的影響忽略不計，雙向網絡編碼可使用更低的計算開銷達到與偵聽網絡編碼類似的性能。

參考文獻

[1] Katti S,Rahul H,Hu W,et al.XORs in the air:Practical wireless network coding[J].IEEE/ACM Transactions on Networking,2008,16(3):497-510.

[2] Sengupta S,Rayanchu S,Banerjee S.An analysis of wireless network coding for unicast sessions:The case for coding-aware routing[C]//26thIEEE International Conference on Compute Communications.Anchorage,AK:INFOCOM,2007:1028-1036.

[3] Lun D S,Ratnakar N,Medard M,et al.Minimum-cost multicast over coded packet networks[J].IEEE Transactions on Information Theory,2008,52(6):2608-2623.

[4] Wu Y,Chou P A,Kung S Y.Minimum-energy multicast in mobile ad hoc networks using network coding[J].IEEE Transactions on Commuhications,2005,53(11):1906-1918.

[5] Cui T,Chen L,Ho T.Energy efficient opportunistic network coding for wireless networks[C]//27thIEEE International Conference on Compute Communications.Phoenix,AZ:INFOCOM,2008:361-365.

[6] 王春雨,張曦煌.Ad Hoc網絡中的基于網絡編碼的無線路由協議研究[J].計算機工程與設計,2013,34(5):1563-1567.

[7] Li S Y R,Yeung R W,Cai N.Linear network coding[J].IEEE Trans.on Information Theory,2003,49(2):371-381.

[8] Ho T,Medard M,Koetter R.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[9] Ho T,Viswanathan H.Dynamic algorithms for multicast with intra-session network coding[J].IEEE Transactions on Information Theory,2009,55(4):797-815.

[10] 葛青,白光偉,沈航,等.無線網絡鏈路質量感知的機會網絡編碼機制[J].計算機科學,2013,35(11):29-34.

[11] Chaporkar P,Proutiere A.Adaptive network coding and scheduling for maximizing throughput in wireless networks[C]//MobiCom’07 proceedings of the 13thannual ACM international coference on Mobile computing and networking.New York,2007:135-146.

[12] Khreishah A,Wang C C,Shroff N B.Cross-layer optimization for wireless multihop networks with pairwise intersession network coding[J].IEEE Journals on Selected Areas in Communications,2009,27(5):606-621.

[13] Madan R,Lall S.Distributed algorithms for maximum lifetime routing in wireless sensor networks[J].IEEE Transactions on Wireless Communications,2009,5(8):2185-2193.

[14] 李繁,金明錄.基于網絡編碼的車載移動網絡數據傳輸優化[J].計算機科學,2013,35(3):170-174,214.

[15] Nagajothy M,Radha D.Network lifetime enhancement in wireless sensor network using network coding[C]//International Conference on Control,Automation,Communication and Energy Conservation,Perundurai,Tamilnadu,2009:1-4.

[16] Hosseinmardi H,Lahouti F.Multicast lifetime maximization using network coding:A cross-layer approach[C]//Proceeding of 24th Biennial Symposium on Communications,Kingston,ON,2008:1-4.

[17] Hong Y,Xu J,Jiang C.Lifetime maximization in wireless sensor networks with network coding[C]//Proceeding IEEE WiCom,Shanghai,2007:2527-2530.

[18] 韓莉,錢煥延.基于網絡編碼的無線多跳網絡多路徑機會路由算法[J].計算機科學,2014,36(5):122-125.

[19] Ding L,Wu P,Wang H,et al.Flow augmenting routing with network coding for lifetime maximization in wireless networks[C]//CHINACOM,Beijing China,2010:1-5.

中圖分類號TP311.12

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.029

收稿日期：2014-06-09。李明，工程師，主研領域：中心機房及虛擬化技術，數據庫與數據安全，網絡通信技術。王睿，助理工程師。馬睿，工程師。汪新建，工程師。童玲，助理工程師。