基于網絡編碼的無線網絡容量分析*

孟利民，張　靜，周　凱，應頌翔（浙江工業(yè)大學信息工程學院，杭州310023）

?

基于網絡編碼的無線網絡容量分析*

孟利民*，張靜，周凱，應頌翔
（浙江工業(yè)大學信息工程學院，杭州310023）

摘要：無線網絡容量一直是無線網絡領域的研究熱點，而網絡編碼通過賦予中間節(jié)點對接收數(shù)據(jù)包進行編碼、組合的能力，可以有效提高網絡容量，達到最大流—最小割定理確定的理論上限。本文在Gupta和Kumar提出的信號干擾噪聲比模型基礎上，首先分析網絡節(jié)點均勻分布時發(fā)送節(jié)點與目的節(jié)點進行多跳傳輸?shù)臒o線網絡容量計算方法；接著推導出了基于網絡編碼的無線網絡容量計算公式，并利用MATLAB中求解線性規(guī)劃問題的函數(shù)linprog（）求解網絡最大流及各鏈路流量，以此求出無線網絡容量上界。通過對無線網絡容量上界進行MATLAB仿真，得到如下結論：無線網絡容量上界隨節(jié)點數(shù)量的增加呈現(xiàn)先增加后減少的趨勢；且當節(jié)點數(shù)量趨于無窮大時，網絡容量趨于零；與傳統(tǒng)的存儲轉發(fā)模式相比，采用網絡編碼有利于提高網絡容量。

關鍵詞：無線網絡；網絡容量；網絡編碼；最大流—最小割定理

網絡容量作為評估無線通信網絡性能的重要參數(shù)可指導無線網絡的優(yōu)化設計，一直是研究的熱點領域。傳統(tǒng)無線通信的容量研究主要建立在特定點對點信道下，尋求達到最佳理論性能界限或信道容量?；邳c對點通信的香農定理在無線蜂窩通信系統(tǒng)中的應用獲得了巨大的成功，但這種方法的主要缺點在于大部分研究成果都只局限于一些簡單的網絡，而難以進行推廣。2000年，Gupta和Kumar［1］等人針對自組織（Ad Hoc）無線網絡下的網絡容量進行分析，建立了獨立同分布下靜態(tài)節(jié)點的無線Ad-hoc網絡模型，明確了無線網絡容量的定義，提出了著名的無線網絡容量計算公式，拉開了無線網絡容量研究的序幕。

在Gupta網絡容量模型基礎上，許多專家提出各種不同的網絡容量定義及相應的網絡容量計算方法［2-5］。郭中華［6］提出基于歐氏最小生成樹的方法，推導了無線網絡單播、多播容量理論值。胡晗［7］依據(jù)隨機幾何理論及泊松過程建立了無線網絡模型，基于不同的調制方式和糾錯編碼方案，分析了無線網絡的中斷概率和網絡容量。Rezagah［8］基于信噪比的累積分布函數(shù)提出了一種網絡容量計算方法并推導出其容量的閉合表達式。在Gupta和Kumar從理論上給出無線網絡容量所能達到的界限后，許多學者努力尋找提高網絡容量的各種方法。文獻［9-10］提出利用節(jié)點的移動特性提高網絡容量的界限，Yi［11］等人討論了在隨機網絡中使用智能天線提高網絡容量界限。此外，還有學者認為可利用基礎設施［12］或者利用超帶寬技術［13］提高網絡容量，文獻［14］則論述了多向轉發(fā)對網絡容量的增益。

另一方面，網絡編碼最早在1998年由香港中文大學Robert Li和Raymond Yeung提出，它拋棄了傳統(tǒng)通信網絡中繼節(jié)點只對接收信息進行存儲和轉發(fā)的思想，賦予網絡節(jié)點對接收數(shù)據(jù)包進行組合、編碼等一系列的智能化處理能力，從而進一步提升網絡容量。Gastpar等采用Gupta提出的網絡模型，在僅考慮中繼業(yè)務通信且網絡中只存在一對發(fā)送節(jié)點與目的節(jié)點的情況下推導得出：若采用復合網絡編碼，則這類網絡的容量在節(jié)點數(shù)目趨近于無窮時近似為Θ(logn)［15］。本文在Gupta無線網絡容量計算方法的基礎上，將多跳傳輸和網絡編碼相結合，提出基于網絡編碼思想的無線網絡容量計算方法。由于采用網絡編碼采用多跳傳輸方式，本文首先分析網絡信息多跳傳輸?shù)倪B通概率及多跳網絡容量計算公式；然后分析采用網絡編碼思想的網絡容量計算方法，最后利用MATLAB中求解線性規(guī)劃問題的函數(shù)linprog（）求解網絡最大流及各鏈路流量，以此求出無線網絡容量上界。

1　網絡模型

2000年，Gupta和Kumar提出了著名的無線網絡容量計算方法。本文采用Gupta信號干擾噪聲比（SINR）模型，令i、j分別表示發(fā)送、接收節(jié)點，l表示同一時刻同一信道向j進行信息傳輸?shù)墓?jié)點。pi表示節(jié)點i的發(fā)送功率，d-ijα表示節(jié)點i到節(jié)點j的信道增益，則節(jié)點j處的接收功率為pid-ijα。在任意時刻，若節(jié)點j處的信號干擾噪聲比滿足如下關系，則節(jié)點i與j之間能夠進行正常的信息傳輸。

式中，η為環(huán)境噪聲功率，β為節(jié)點成功傳輸?shù)腟INR閾值。

只考慮一個系統(tǒng)中，在中斷約束下，無線網絡容量表示為單位面積內網絡的頻譜資源利用率，即鏈路成功傳輸概率和網絡節(jié)點密度乘積。

其中，N表示網絡節(jié)點總數(shù)量，S表示網絡總面積，ε表示鏈路傳輸?shù)闹袛喔怕剩?/p>

上述無線網絡容量計算公式是在分析具有典型意義的單跳鏈路的基礎上得到的。該網絡容量公式適用于單跳無線網絡，具有一定的局限性。由于采用網絡編碼采用多跳傳輸方式，本文首先分析網絡信息多跳傳輸?shù)倪B通概率及多跳網絡容量計算公式。

2　多跳網絡容量分析

無線網絡中每個節(jié)點都有一定的傳輸半徑，當目的節(jié)點在發(fā)送節(jié)點傳輸范圍之內時，兩點可直接通信，即通過單跳傳輸［16］。當目的節(jié)點與發(fā)送節(jié)點之間距離大于傳輸半徑時，則必須通過中間節(jié)點進行通信，即通過多跳無線網絡通信［17］。

假設節(jié)點均勻分布的無線網絡面積為S，網絡節(jié)點總數(shù)為N，每個節(jié)點都有相同的固定傳輸半徑R。圖1表明接收節(jié)點在發(fā)送節(jié)點傳輸范圍之內，即任意兩點通過一跳傳輸?shù)母怕时磉_如下：

圖1　單跳傳輸網絡

當發(fā)送節(jié)點s與目的節(jié)點d之間的距離大于通信半徑而小于兩倍通信半徑時，需要1個中間節(jié)點進行轉發(fā)。即發(fā)送節(jié)點s與目的節(jié)點d通過兩跳傳輸?shù)母怕时磉_如下：

圖2　兩跳傳輸網絡

同理，當發(fā)送節(jié)點s與目的節(jié)點d之間的距離大于兩倍通信半徑而小于三倍通信半徑時，需要2個中間節(jié)點進行轉發(fā)。即發(fā)送節(jié)點s與目的節(jié)點d通過三跳連通的概率為

不失一般性，網絡四跳連通概率即發(fā)送節(jié)點s與目的節(jié)點d通過三個中間節(jié)點轉發(fā)的概率表達如下：

本文對網絡節(jié)點連通性進行MATLAB仿真。在500 m×500 m的無線網絡面積中，節(jié)點位置服從均勻分布且傳輸半徑均為80 m。針對不同數(shù)量的節(jié)點，分別計算網絡兩跳、三跳、四跳連通概率，如圖（3）所示。仿真結果表明：無線網絡連通概率隨節(jié)點數(shù)量增加而增加，并逐漸趨于飽和；當節(jié)點數(shù)量小于10時，兩跳連通概率優(yōu)于三跳、四跳連通概率，而節(jié)點數(shù)量大于10時，跳數(shù)越多，連通性越好。

圖3　網絡連通性與節(jié)點數(shù)量關系示意圖

在多跳網絡連通性的基礎上，多跳無線網絡容量可進一步表示為多跳連通概率、網絡成功傳輸概率和網絡節(jié)點密度的乘積，即i跳無線網絡容量為

3　基于網絡編碼的網絡容量分析

網絡編碼是Robert Li等人于1998年提出的一種網絡數(shù)據(jù)傳輸方式。在傳統(tǒng)的路由網絡中，網絡節(jié)點只能對數(shù)據(jù)進行復制和轉發(fā)，而在基于網絡編碼的網絡中，網絡節(jié)點可對接收到的數(shù)據(jù)進行組合、編碼操作，再將結果復制或轉發(fā)，從而利用網絡節(jié)點的計算資源來換取帶寬利用率，提高網絡吞吐量。

Gupta等人提出的網絡容量計算方法都是假設端到端傳輸?shù)男畔閱挝槐忍?，在引入網絡編碼后，端到端吞吐量會明顯增加，信息傳輸速率可達到最大流—最小割定理確定的理論上限［18］。如圖4所示的蝶形網絡，源節(jié)點S可以選擇兩條邊不相交的路徑S→V1→T1和S→V1→V3→V4→T1傳輸不同信息到達目的節(jié)點T1。同理，源節(jié)點S可以選擇兩條邊不相交的路徑S→V2→T2和S→V2→V3→V4→T2傳輸不同信息到達目的節(jié)點T2。若采用傳統(tǒng)的路由轉發(fā)策略，則傳輸鏈路V3V4為瓶頸鏈路，不能同時轉發(fā)兩個不同的信息比特。若允許中間節(jié)點對接收到的信息進行編碼處理，則鏈路SV1，V1T1，V1V3傳輸比特?b1，鏈路SV2，V2T2，V2V3傳輸比特b2，鏈路V3V4，V4T1，V4T2傳輸比特b1⊕b2。則節(jié)點T1可收到?b1和?b1⊕b2，通過信息解碼，可得到b1和b2。同理，節(jié)點T2也可得到b1和b2。

本文在上述無線網絡容量計算方法的基礎上繼續(xù)討論基于網絡編碼的無線網絡容量。當引入網絡編碼后，發(fā)送節(jié)點與目的節(jié)點的鏈路流量不能再簡單地假設為1。故無線網絡容量計算公式可以表達為。其中，c表示發(fā)送節(jié)點到目的節(jié)點傳輸?shù)男畔⒈忍財?shù)。

圖4　網絡編碼

由于采用網絡編碼可以達到最大流—最小割定理確定的理論上限，故我們可以計算發(fā)送節(jié)點到目的節(jié)點的最大流，以及各鏈路流量，從而得出無線網絡容量的上界。

求解網絡最大流及各鏈路流量可以歸結為MATLAB中求解線性規(guī)劃的問題［19］。在MATLAB中求解線性規(guī)劃問題的函數(shù)為linprog（），用于解決以下優(yōu)化問題：

其函數(shù)調用格式為[x，fval，exitflag]= linprog(f，A，b，Aeq，beq，lb，ub)：輸入?yún)?shù)f為目標函數(shù)，以目標函數(shù)的系數(shù)的列向量形式存在；Α和b為不等式約束條件的數(shù)據(jù)矩陣；Aeq和beq為等式約束條件的數(shù)據(jù)矩陣；參數(shù)lb和ub為自變量的范圍。函數(shù)返回的參數(shù)x為線性規(guī)劃的最優(yōu)解；fval為最優(yōu)解x處的函數(shù)值；exitflag為解的輸出標志，當找到最優(yōu)解時，exitflag=1，當線性規(guī)劃無解時，exitflag=-1。

如蝶形網絡圖5所示，各鏈路xi都有相應的容量，假設各鏈路流量分別為x1、x2、x3、…、x11，可利用MATLAB中線性規(guī)劃方法確定從發(fā)送節(jié)點S到目的節(jié)點T的最大流，并求解相應鏈路的流量值。

由于網絡的流入量等于網絡的流出量，所以x1+x2=x5+x7+x8+x9。我們需要求解g=x1+x2的最大值，即目標函數(shù)f=-x1-x2的最小值。除了發(fā)送節(jié)點和目的節(jié)點，其他中間節(jié)點的流入量等于流出量，即

圖5　網絡圖

假設各鏈路的容量為wi，(i=1，2，L，8，9)，則各鏈路流量不大于其容量，即

由（10）可得，Aeq·x=beq，其中

由（11）可知，

通過MATLAB仿真[x，fval，exitflag]= linprog(f，[ ]，[ ]，Aeq，beq，lb，ub)，得fval=-37.2052，x= ［18.1472 19.0579 3.2895 7.3578 14.8578 10.6473 11.7001 4.3624 6.2849］。即最大值g=37，相應鏈路流量x1=18.1，x2=19.0，x3=3.2，x4=7.3，x5=14.8，x6= 10.6，x7=11.7，x8=4.3，x9=6.2，如圖6所示。

由圖6可知，若采用傳統(tǒng)的路由轉發(fā)策略，源節(jié)點S可經路徑S→V1→T1傳輸14.8比特信息到目的節(jié)點T1，經路徑S→V2→T2傳輸11.7比特到目的節(jié)點T2。而采用網絡編碼方案，源節(jié)點S可以選擇路徑S→V1→T1和S→V1→V3→V4→T1傳輸14.8+4.3= 19.1比特信息到達目的節(jié)點T1，同時源節(jié)點S經路徑S→V2→T2和S→V2→V3→V4→T2傳輸11.7+6.2= 17.9比特信息到達目的節(jié)點T2。所以，網絡容量為。其中，ci、pi、(1-εi)分別為發(fā)送節(jié)點到目的節(jié)點的i條路徑中各自的傳輸信息比特、連通概率和成功傳輸概率。

圖6　流量網絡圖

假設信道信噪比閾值為1.3，α=2，信道環(huán)境噪聲忽略不計。在無線網絡面積為500 m×500 m，節(jié)點通信半徑為80 m和無線網絡面積為400 m× 400 m，節(jié)點通信半徑為60 m兩種情況下，我們分別對無線網絡容量上限進行仿真，如圖7所示。

圖7　無線網絡面積為500 m×500 m，節(jié)點通信半徑為80 m時網絡容量上界仿真圖

圖8　無線網絡面積為400 m×400 m，節(jié)點通信半徑為60 m時網絡容量上界仿真圖

從圖中可以發(fā)現(xiàn)：每條曲線都呈現(xiàn)出無線網絡容量上界隨節(jié)點數(shù)量的增加呈現(xiàn)先增加后減少的趨勢且當節(jié)點數(shù)量趨于無窮大時，網絡容量趨于零，這也與Gupta的結論相一致，即網絡中節(jié)點數(shù)目的增加是以容量的減少為代價；與傳統(tǒng)存儲轉發(fā)模式相比，采用網絡編碼有利于提高無線網絡容量。

4　結束語

在Gupta信噪比網絡容量模型的基礎上，本文提出了一種基于網絡編碼的無線網絡容量計算方法。Gupta信噪比網絡容量模型假設發(fā)送節(jié)點到目的節(jié)點的信息傳輸比特為1，而網絡編碼會提高端到端的吞吐量，計算發(fā)送節(jié)點到目的節(jié)點的信息傳輸比特數(shù)可以更精確地描述無線網絡容量。采用網絡編碼必會經過多跳傳輸，本文首先分析了網絡的多跳連通性及多跳網絡容量計算，隨后提出基于網絡編碼的無線網絡容量計算公式，并利用MATLAB中求解線性規(guī)劃的方法得出利用網絡編碼可達到的最大流及各鏈路流量，由此可知發(fā)送節(jié)點到目的節(jié)點的幾條路徑各自傳輸?shù)男畔⒈忍財?shù)，并求出無線網絡容量上界。通過仿真發(fā)現(xiàn)：無線網絡容量上界隨節(jié)點數(shù)量的增加呈現(xiàn)先增加后減少的趨勢，且當節(jié)點數(shù)量趨于無窮大時，網絡容量趨于零，即網絡中節(jié)點數(shù)目的增加是以容量的減少為代價；與傳統(tǒng)存儲轉發(fā)模式相比，采用網絡編碼有利于提高無線網絡容量。

參考文獻：

［1］Gupta Piyush，Kumar P R. The Capacity of Wireless Networks［J］. IEEE Transactions on Information Theory，2000，46(2)：388-404.

［2］Hwang Y J，Seong Lyun Kim. The Capacity of Random Wireless Networks［J］. IEEE Transactions on Wireless Communications，2008，7(12)：4968-4975.

［3］Dousse O，F(xiàn)ranceschetti M，Thiran P. On the Throughput Scaling of Wireless Relay Networks［J］. IEEE Transactions on Informa?tion Theory，2006，52(6)：2756-761.

［4］周凱，孟利民，華驚宇.基于Grover路由策略的無線傳感網絡剩余容量構造與研究［J］.傳感技術學報，2015，28(2)：249-253.

［5］Kannan S，Viswanath P. Capacity of Multiple Unicast in Wireless Networks：A Polymatroidal Approach［J］. IEEE Transactions on Information Theory，2014，60(10)：6303-6328.

［6］郭中華，史浩山.基于歐式最小生成樹的無線Ad Hoc網絡容量研究［J］.傳感技術學報，2008，21(10)：1750-1754.

［7］胡晗，朱洪波，朱琦.無線Ad hoc網絡傳輸容量的性能分析［J］.電子與信息學報，2012，34(6)：1457-1462.

［8］Rezagah R E，Mohammadi A. Analyzing the Capacity of Wireless Ad Hoc Networks［J］. Telecommunication Systems，2014，55(1)：159-167.

［9］Grossglauser M，Tse D N C. Mobility Increases the Capacity ofAd-Hoc Wireless Networks［J］. IEEE Transaction on Networking，2002，3：1577-1586.

［10］Jae Young Seol，Seong Lyun Kim. Node Mobility and Capacity in Wireless Controllable Ad hoc Networks［J］. Computer Communi?cations，2012，35(11)：1345-1354.

［11］Yi S，Pei Y，Kalyanaraman S. On the Capacity Improvement of Ad- Hoc Wireless Networks Using Directional Antennas［C］// ACM MobiHoc 2003. New York，2003. 108-116.

［12］Dousse O，Thiran P，Hasler M. Connectivity in Ad-Hoc and Hy?brid Networks［C］// IEEE INFOCOM 2002. 21st Annual Joint Conference of the IEEE Computer and Communications Societies. New York，2002. 1079-1088.

［13］Negi R，Rajeswaran A. Capacity of Power Constrained Ad- Hoc Network［C］// IEEE INFOCOM 2004. 23rd Annual Joint Confer?ence of the IEEE Computer and Communications Societies. Hong Kong，2004. 443-453.

［14］Nousiainen J，Virtamo J，Lassila P. Impact of Multidirectional For?warding on the Capacity of Large Wireless Networks［J］. IEEE Communications Letters，2014，18(2)：372-375.

［15］Gastpar M，Vetterli M. On the Capacity of Wireless Networks：the Relay Case［C］// IEEE INFOCOM 2002. 21st Annual Joint Con?ference of the IEEE Computer and Communications Societies. New York，2002. 1577-1586.

［16］劉少陽，趙海濤，魏急波，等.多跳無線網絡中路徑端到端容量的準確計算［J］.軟件學報，2013，24(1)：164-174.

［17］夏少波，鄒建梅，朱曉麗，等.基于跳數(shù)區(qū)域劃分的DV-Hop改進算法［J］.傳感技術學報，2014，27(7)：964-969.

［18］樊平毅.網絡信息論［M］.北京：清華大學出版社，2009. 126-127.

［19］王薇. MATLAB從基礎到精通［M］.北京：電子工業(yè)出版社，2012. 363-364.

孟利民（1963-），女，教授，博士生導師，信息與通信工程專業(yè)工學博士，浙江工業(yè)大學信息與通信系統(tǒng)研究所所長，浙江省光纖通信技術重點實驗室主任。主要研究方向為無線通信與網絡、多媒體數(shù)字通信、網絡通信與控制通信信號處理與軟件無線電，mlm@zjut.edu.cn；

張靜（1989-），女，碩士研究生，就讀于浙江工業(yè)大學信息工程學院，主要研究方向：無線網絡容量計算、網絡編碼，zjing890921@163.com。

Timing Signal Subsection Compression Algorithm in WSNs Based on Compressed Sensing Theory*

LIUZhouzhou1，XUJiliang2，HAN Yin3，WANGXiaozhu
（1.Xi’an Aeronautical University，Xi’an 710077，China；2.Air Force Xi'an Flight Academy Fifth Training Brigade，Nanchong Sichuan 637100，China；3.Chinese Electronics Import and Export Corporation，Beijing 100036，China）

Abstract：For compressive sensing（CS）application timing signal during transmission in the wireless sensor net?works has low compression ratio，high energy consumption of communication，the timing signal segment compres?sion algorithms is proposed to solve the unknown signal sparsity and high sparsity under conditions of low compres?sive sensing reconstruction efficiency data reconstruction algorithm when the reconstruction accuracy is poor. As the basis of segmentation，the number of non zero elements is collected in the data，by reducing the number of com?binations of nonzero elements within the segment to improve the accuracy of signal reconstruction，while taking ad?vantage of the characteristics of compressive sensing theory to achieve a high compression ratio of the signal. Experi?mental results show that，under the chaotic quantum clonal Reconstruction（Q-CSDR）algorithm as the reconstruc?tion algorithm，the blind signal sparsity and sparse conditions is higher than 40，the compression ratio can be great?er than 0.4，the signal has been compressed，and square error of less than 0.01 of its reconstructed signal，and the network lifetime is prolonged by about 2 times.

Key words：wireless sensor networks；compressive sensing theory；the timing signal；sparsity；compression ratio

doi：EEACC：7230；7230V10.3969/j.issn.1004-1699.2016.01.021

收稿日期：2015-07-28修改日期：2015-10-05

中圖分類號：TP393.0

文獻標識碼：A

文章編號：1004-1699（2016）01-0116-06

項目來源：國家自然科學基金項目（61372087）