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

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

?

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

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

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

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

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

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

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

1　網絡模型

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

式中，η為環境噪聲功率，β為節點成功傳輸的SINR閾值。

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

其中，N表示網絡節點總數量，S表示網絡總面積，ε表示鏈路傳輸的中斷概率，即

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

2　多跳網絡容量分析

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

假設節點均勻分布的無線網絡面積為S，網絡節點總數為N，每個節點都有相同的固定傳輸半徑R。圖1表明接收節點在發送節點傳輸范圍之內，即任意兩點通過一跳傳輸的概率表達如下：

圖1　單跳傳輸網絡

當發送節點s與目的節點d之間的距離大于通信半徑而小于兩倍通信半徑時，需要1個中間節點進行轉發。即發送節點s與目的節點d通過兩跳傳輸的概率表達如下：

圖2　兩跳傳輸網絡

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

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

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

圖3　網絡連通性與節點數量關系示意圖

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

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

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

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

本文在上述無線網絡容量計算方法的基礎上繼續討論基于網絡編碼的無線網絡容量。當引入網絡編碼后，發送節點與目的節點的鏈路流量不能再簡單地假設為1。故無線網絡容量計算公式可以表達為。其中，c表示發送節點到目的節點傳輸的信息比特數。

圖4　網絡編碼

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

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

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

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

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

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

圖6　流量網絡圖

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

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

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

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

4　結束語

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

參考文獻：

［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，Franceschetti 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］夏少波，鄒建梅，朱曉麗，等.基于跳數區域劃分的DV-Hop改進算法［J］.傳感技術學報，2014，27(7)：964-969.

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

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

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

張靜（1989-），女，碩士研究生，就讀于浙江工業大學信息工程學院，主要研究方向：無線網絡容量計算、網絡編碼，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）