基于網(wǎng)絡(luò)編碼的無線多跳網(wǎng)絡(luò)壽命優(yōu)化模型研究

李　明　王　?！●R　睿　汪新建　童　玲

(中國(guó)人民解放軍成都軍區(qū)總醫(yī)院網(wǎng)絡(luò)管理中心　四川 成都 610083)

?

基于網(wǎng)絡(luò)編碼的無線多跳網(wǎng)絡(luò)壽命優(yōu)化模型研究

李明王睿馬睿汪新建童玲

(中國(guó)人民解放軍成都軍區(qū)總醫(yī)院網(wǎng)絡(luò)管理中心四川 成都 610083)

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

關(guān)鍵詞壽命優(yōu)化無線多跳網(wǎng)絡(luò)網(wǎng)絡(luò)編碼線性規(guī)劃隨機(jī)拓?fù)淠Ｐ?/p>

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引言

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

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

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

1基本原理與模型

1.1網(wǎng)絡(luò)模型

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

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

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

1.2網(wǎng)絡(luò)編碼

本文考慮單跳網(wǎng)絡(luò)中使用的線性異或網(wǎng)絡(luò)編碼方式，該編碼方式與c=a⊕b類似。這里，a和b為輸入分組，c為異或之后的輸出分組?；趦煞?hào)(分組)的網(wǎng)絡(luò)編碼占COPE的50%以上，占COPR的99%以上[12]。另外，對(duì)實(shí)際系統(tǒng)的研究也發(fā)現(xiàn)多于兩個(gè)符號(hào)的網(wǎng)絡(luò)編碼運(yùn)算會(huì)使優(yōu)化過程極其復(fù)雜。因此，本文對(duì)網(wǎng)絡(luò)編碼的分析將在使用線性異或網(wǎng)絡(luò)編碼的單跳成對(duì)網(wǎng)絡(luò)中進(jìn)行。對(duì)于超過兩個(gè)符號(hào)的網(wǎng)絡(luò)編碼，可以通過伺機(jī)方式，如在COPE和COPR中來實(shí)現(xiàn)。

下面的引理給出了單跳成對(duì)網(wǎng)絡(luò)編碼正常工作的要求。

引理1在單跳網(wǎng)絡(luò)編碼中，對(duì)于節(jié)點(diǎn)k，若想從節(jié)點(diǎn)i傳輸?shù)木幋a分組Pc=Px⊕P解碼出分組Px，則該節(jié)點(diǎn)需滿足以下兩個(gè)條件：1) 節(jié)點(diǎn)k從節(jié)點(diǎn)i接收到分組Pc；2) 節(jié)點(diǎn)k獲得了未編碼分組P。

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

圖1　單跳網(wǎng)絡(luò)編碼

由于單跳網(wǎng)絡(luò)編碼同時(shí)涉及到前跳節(jié)點(diǎn)和后跳節(jié)點(diǎn)，為了描述的簡(jiǎn)便，本文定義了一種雙跳鏈路。

定義1(雙跳鏈路)對(duì)于節(jié)點(diǎn)i，從節(jié)點(diǎn)j到節(jié)點(diǎn)k經(jīng)過節(jié)點(diǎn)i的鏈路稱為節(jié)點(diǎn)i處的雙跳鏈路，記為(j,i,k),j≠k。

需要注意的是，對(duì)于從源節(jié)點(diǎn)開始的傳輸，有j=i，而對(duì)于目的節(jié)點(diǎn)的接收，有i=k。

從上面的定義和描述可以看出，單跳網(wǎng)絡(luò)編碼依賴于鄰居節(jié)點(diǎn)的相對(duì)位置。例如，在圖1(b)中，雙向鏈路(j,i,k)和(m,i,n)可以同時(shí)進(jìn)行編碼，這是因?yàn)楣?jié)點(diǎn)k和n可以分別偵聽到節(jié)點(diǎn)m和j的數(shù)據(jù)。而雙跳網(wǎng)絡(luò)(j,i,k)和(n,i,m)就不能同時(shí)編碼。由此可以得到可同時(shí)進(jìn)行網(wǎng)絡(luò)編碼的雙向鏈路在幾何上的結(jié)構(gòu)定義。

定義2(網(wǎng)絡(luò)編碼結(jié)構(gòu))網(wǎng)絡(luò)編碼結(jié)構(gòu)指的是在幾何上能夠同時(shí)編碼的雙向鏈路的有序集合。

使用上述定義和簡(jiǎn)記法，可以表述下述引理，以確定一種網(wǎng)絡(luò)編碼情況是雙向網(wǎng)絡(luò)編碼還是偵聽網(wǎng)絡(luò)編碼。

引理2Si是雙向網(wǎng)絡(luò)編碼結(jié)構(gòu),當(dāng)且僅當(dāng)p(Si)=n(Si)，而Si是偵聽網(wǎng)絡(luò)編碼結(jié)構(gòu),當(dāng)且僅當(dāng)p(Si)≠n(Si)。

1.3網(wǎng)絡(luò)壽命

網(wǎng)絡(luò)壽命指的是網(wǎng)絡(luò)運(yùn)行良好，尤其是滿足網(wǎng)絡(luò)所有需求的持續(xù)時(shí)間。以前的研究對(duì)不同應(yīng)用場(chǎng)景下的網(wǎng)絡(luò)壽命提出了多種定義，例如所有節(jié)點(diǎn)的最小壽命、壽命向量等。為了簡(jiǎn)化分析，本文采用了第一種定義，并將其擴(kuò)展，以使其適合文中分析網(wǎng)絡(luò)編碼的情況。

(1)

其中，第一項(xiàng)為節(jié)點(diǎn)i處的傳輸數(shù)據(jù)流c的功率消耗，第二項(xiàng)是從所有鄰節(jié)點(diǎn)j∈V接收的數(shù)據(jù)流c的功率消耗，第三項(xiàng)是偵聽的接收功率消耗。需要注意的是，對(duì)于一個(gè)網(wǎng)絡(luò)編碼結(jié)構(gòu)Sj，節(jié)點(diǎn)i處的偵聽條件為i∈n(Sj)，而i?p(Sj)。

節(jié)點(diǎn)i處的壽命就可表示為：

(2)

其中，網(wǎng)絡(luò)壽命由節(jié)點(diǎn)i的能量Ei和節(jié)點(diǎn)i處理所有分組所消耗的功率決定。由此得到整個(gè)網(wǎng)絡(luò)的壽命：

(3)

2基于網(wǎng)絡(luò)編碼的無線多跳網(wǎng)絡(luò)壽命優(yōu)化模型

對(duì)無網(wǎng)絡(luò)編碼情形、雙向網(wǎng)絡(luò)編碼情形和偵聽網(wǎng)絡(luò)編碼情形下的網(wǎng)絡(luò)壽命優(yōu)化問題進(jìn)行模型化描述。其中，無網(wǎng)絡(luò)編碼情形下的優(yōu)化問題是另外兩種情形的基準(zhǔn)。本文提出了一種新的公式化描述方法，該方法從節(jié)點(diǎn)和本地?cái)?shù)據(jù)流的角度對(duì)優(yōu)化問題進(jìn)行描述，并具有低復(fù)雜度。

2.1無網(wǎng)絡(luò)編碼情形

無網(wǎng)絡(luò)編碼情形下，優(yōu)化問題的約束與流量守恒法則、總能量限制、每條鏈路的可達(dá)速率域以及整個(gè)網(wǎng)絡(luò)有關(guān)。這種情形下，壽命優(yōu)化問題可表述為：

maxT

(4)

(5)

(6)

(rij)∈Co(r)

(7)

(8)

其中，xc為數(shù)據(jù)流c的流量需求。

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

當(dāng)鏈路速率足夠大以使所有鏈路都能同時(shí)滿足速率需求時(shí)，網(wǎng)絡(luò)壽命就不會(huì)受干擾模型和調(diào)度算法的影響。由于對(duì)于流量需求相對(duì)較小的能量受限的無線網(wǎng)路通常滿足這個(gè)條件，因此如式(6)和式(7)所示的速率約束可以忽略不計(jì)。優(yōu)化問題可簡(jiǎn)化為：

maxT

(9)

(10)

2.2雙向網(wǎng)絡(luò)編碼情形

maxT

(11)

(12)

(13)

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

2.3偵聽網(wǎng)絡(luò)編碼情形

除了雙向網(wǎng)絡(luò)編碼中的約束，偵聽網(wǎng)絡(luò)編碼還需對(duì)前跳節(jié)點(diǎn)提出要求。為了正確解碼使用偵聽的分組，未編碼數(shù)據(jù)的偵聽速率應(yīng)當(dāng)大于總編碼速率。故該情形下的壽命最優(yōu)化問題可表述為：

maxT

(14)

(15)

(16)

(17)

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

2.4動(dòng)態(tài)路由算法優(yōu)化

在有網(wǎng)絡(luò)編碼場(chǎng)景下，為了優(yōu)化網(wǎng)絡(luò)的壽命，使用動(dòng)態(tài)路由算法對(duì)網(wǎng)絡(luò)的拓?fù)溥M(jìn)行優(yōu)化，進(jìn)而可以使節(jié)點(diǎn)傳輸數(shù)據(jù)所需的路由更短，從而優(yōu)化了網(wǎng)絡(luò)的壽命。

在動(dòng)態(tài)路由算法中，節(jié)點(diǎn)i的周期消耗可表示為：

(18)

其中，Ni為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合，xij為節(jié)點(diǎn)i向節(jié)點(diǎn)j發(fā)送的信息數(shù)量，rij,tij分別為收發(fā)信息的能量損失系數(shù)，從而得到節(jié)點(diǎn)i的壽命：

(19)

其中bi為節(jié)點(diǎn)i的剩余能量。

從而網(wǎng)絡(luò)壽命可定義為：

(20)

其中，(0,i)∈E表示鏈路(0,i)為網(wǎng)絡(luò)中從原點(diǎn)到節(jié)點(diǎn)i的一條鏈路。

應(yīng)用線性規(guī)劃最大最小網(wǎng)絡(luò)中的節(jié)點(diǎn)壽命：

?i∈N?j∈Ni

(21)

動(dòng)態(tài)路由算法描述如下：

1) 初始化：獲取網(wǎng)絡(luò)的拓?fù)湫畔ⅲ琸=1；

2) 執(zhí)行式(21)的線性規(guī)劃過程，獲取節(jié)點(diǎn)的路由信息；

3) 當(dāng)網(wǎng)絡(luò)中有節(jié)點(diǎn)因能量耗盡而失效時(shí)，更新網(wǎng)絡(luò)拓?fù)洌绻嬖诨镜囊惶?jié)點(diǎn)，則轉(zhuǎn)2)，k=k+1；

3仿真實(shí)驗(yàn)與分析

可采用性能評(píng)估的集中式解法[2]、對(duì)偶子梯度方法[3,13]和啟發(fā)式流量擴(kuò)張路由法[14,19]來研究性能的評(píng)估，這里采用第一種方法。針對(duì)不同的能量分布的配置、業(yè)務(wù)需求、數(shù)據(jù)流個(gè)數(shù)和功率控制模型開展網(wǎng)絡(luò)壽命和計(jì)算開銷方面的評(píng)估工作。

3.1參數(shù)設(shè)置

為了深入分析網(wǎng)絡(luò)編碼對(duì)壽命的影響，使用簡(jiǎn)單功率消耗模型。假設(shè)所有節(jié)點(diǎn)的物理特性和電氣特性都是相同的且信道衰落為參數(shù)α=4的指數(shù)平坦衰落，則將一個(gè)比特從節(jié)點(diǎn)i傳輸?shù)焦?jié)點(diǎn)j的能量消耗僅依賴于節(jié)點(diǎn)之間的距離和收發(fā)器的功率消耗。發(fā)送和接收的功率消耗可寫為：

(22)

(23)

3.2網(wǎng)絡(luò)壽命和性能仿真

該部分將評(píng)估一個(gè)基于多約束編碼的無線多跳網(wǎng)絡(luò)壽命性能。在80 m×80 m的正方形區(qū)域內(nèi)隨機(jī)放置20個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)的平均度數(shù)為2.8。假設(shè)每個(gè)節(jié)點(diǎn)的初始能量服從均值為P的指數(shù)分布。每個(gè)節(jié)點(diǎn)產(chǎn)生16個(gè)數(shù)據(jù)流，且源節(jié)點(diǎn)從20個(gè)節(jié)點(diǎn)中隨機(jī)選擇。假定所有的數(shù)據(jù)流都具有合適的路徑，即每個(gè)數(shù)據(jù)流的源節(jié)點(diǎn)和匯聚節(jié)點(diǎn)都是相連的。

為了評(píng)估協(xié)議模型和物理模型下網(wǎng)絡(luò)壽命和計(jì)算開銷的性能。所有仿真都運(yùn)行50次且性能指標(biāo)的均值和方差都?xì)w一到無網(wǎng)絡(luò)編碼情形下的對(duì)應(yīng)值。

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

圖2　在物理和功率協(xié)議模型下，使用雙向和偵聽網(wǎng)絡(luò)編碼的歸一化壽命隨不同數(shù)據(jù)流個(gè)數(shù)的變化情況

2) 計(jì)算開銷:使用迭代次數(shù)來評(píng)估優(yōu)化問題的計(jì)算開銷，仿真結(jié)果如圖3所示。由圖可知：(1) 兩種功率控制模型下，迭代次數(shù)隨著數(shù)據(jù)流個(gè)數(shù)的增加而增加；(2) 物理模型下的迭代次數(shù)比協(xié)議模型下的迭代次數(shù)高；(3) 使用偵聽網(wǎng)絡(luò)編碼的迭代次數(shù)要高于使用雙向網(wǎng)絡(luò)編碼的迭代次數(shù)。

圖3　迭代次數(shù)隨數(shù)據(jù)流個(gè)數(shù)的變化情況

3) 初始能量的影響:雙向網(wǎng)絡(luò)編碼和偵聽網(wǎng)絡(luò)編碼歸一化壽命的編碼機(jī)制涉及兩種不同的初始能量配置，即P=1和P=5。不同初始能量配置下的兩類模型的網(wǎng)絡(luò)壽命如圖4所示。圖中，物理功率控制模型和協(xié)議功率控制模型分別用Phy，Pro表示，雙向網(wǎng)絡(luò)編碼方式和偵聽網(wǎng)絡(luò)編碼方式分別用2W和OH表示?？梢园l(fā)現(xiàn)壽命均隨著數(shù)據(jù)流個(gè)數(shù)的增加而增加，但壽命和初始能量之間并不存在簡(jiǎn)單的對(duì)應(yīng)關(guān)系。

圖4　不同初始能量，網(wǎng)絡(luò)編碼機(jī)制和功率控制模型下的網(wǎng)絡(luò)壽命

4) 業(yè)務(wù)非對(duì)稱性的影響: 假設(shè)所有數(shù)據(jù)流的業(yè)務(wù)需求都是相等的，而實(shí)際網(wǎng)絡(luò)中這種對(duì)稱網(wǎng)絡(luò)不存在，故需研究業(yè)務(wù)非對(duì)稱性對(duì)隨機(jī)拓?fù)渚W(wǎng)絡(luò)壽命的影響。設(shè)定P=5，假設(shè)每個(gè)數(shù)據(jù)流的業(yè)務(wù)需求服從均值為F的指數(shù)分布。不同功率控制模型、網(wǎng)絡(luò)編碼機(jī)制和均值情況下的壽命仿真結(jié)果如圖5所示。由圖可知：雙向和偵聽網(wǎng)絡(luò)編碼機(jī)制的性能相近，與流量需求的平均值無關(guān)。

圖5　不同業(yè)務(wù)需求，網(wǎng)絡(luò)編碼機(jī)制和功率控制模型下的壽命

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

4結(jié)語

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

參考文獻(xiàn)

[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網(wǎng)絡(luò)中的基于網(wǎng)絡(luò)編碼的無線路由協(xié)議研究[J].計(jì)算機(jī)工程與設(shè)計(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] 葛青,白光偉,沈航,等.無線網(wǎng)絡(luò)鏈路質(zhì)量感知的機(jī)會(huì)網(wǎng)絡(luò)編碼機(jī)制[J].計(jì)算機(jī)科學(xué),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] 李繁,金明錄.基于網(wǎng)絡(luò)編碼的車載移動(dòng)網(wǎng)絡(luò)數(shù)據(jù)傳輸優(yōu)化[J].計(jì)算機(jī)科學(xué),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] 韓莉,錢煥延.基于網(wǎng)絡(luò)編碼的無線多跳網(wǎng)絡(luò)多路徑機(jī)會(huì)路由算法[J].計(jì)算機(jī)科學(xué),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.

中圖分類號(hào)TP311.12

文獻(xiàn)標(biāo)識(shí)碼A

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

收稿日期：2014-06-09。李明，工程師，主研領(lǐng)域：中心機(jī)房及虛擬化技術(shù)，數(shù)據(jù)庫與數(shù)據(jù)安全，網(wǎng)絡(luò)通信技術(shù)。王睿，助理工程師。馬睿，工程師。汪新建，工程師。童玲，助理工程師。