節點傳輸半徑對無線自組織網絡容量的影響分析

摘 要：在共享無線信道的多跳無線自組織網絡中，節點傳輸半徑的大小直接影響節點的一跳吞吐量和業務流傳輸的中繼所需跳數，從而影響網絡容量。在網絡業務類型一致的條件下，通過數學模型分析和仿真實驗，考察了網絡容量與節點傳輸半徑、業務流傳輸的路徑長度以及網絡節點數量之間的關系，其分析結果有助于優化無線網絡的組網結構。

關鍵詞：無線自組織網絡；傳輸半徑；網絡容量

中圖分類號：TP393.12 文獻標志碼：A 文章編號：1001-3695(2008)08-2491-04

Analysis of transmission range impact on throughput performance

in multi-hop wireless networks

MAO Jian-bing， MAO Yu-ming， LENG Su-peng

(School of Communication Information Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:In multi-hop wireless Ad hoc networks where nodes shared the available wireless bandwidth，transmission range had significant effect on the one-hop throughput of a node and the number of hops a traffic flow need to traverse，and consequently affected the capacity of the whole network.Assumed uniform traffic pattern，this paper examined the influence of transmission range，path length of traffic flows and node number on network capacitythrough an analytical model and simulation experiments.The result is helpful for optimizing the structure of multi-hop wireless networks.

Key words:Ad hoc wireless networks; transmission range; network capacity

多跳無線自組織網絡是一種不需要固定網絡基礎設施的無中心結構網絡。當網絡中互相通信的兩個節點在彼此的通信范圍之外時，源節點和目的節點之間通信的分組需要由中間其他節點進行路由轉發，直到分組送達目的節點。在共享無線信道的無線自組織網絡中，無線信號的廣播傳播方式決定了節點之間的通信存在相互干擾。較小的節點傳輸半徑可以降低不同收發節點對之間的互相干擾，提高信道的空間重用率，但是分組需要經過更多跳的無線中繼才能從源節點到達目的節點。反之，較大的傳輸半徑使得每個節點的干擾范圍增大，共同參與信道競爭的節點也隨之增多，造成每個節點的可利用信道帶寬減少。但是，同一源和目的節點之間的分組所需的轉發跳數隨傳輸半徑增大而減少了。

文獻[1]開創性地對無線網絡的容量（網絡中所有業務流的端到端吞吐量的總和）進行了分析，得出了無線網絡的容量隨著節點數量增加的變化關系。當節點分布密度一定時，網絡一跳容量（網絡中所有節點一跳傳輸的吞吐量總和）與網絡節點數量n的關系是o(n)。盡管如此，隨著網絡的增大，通信的源節點和目的節點之間的跳數也相應地增加。如果節點傳輸半徑保持不變，從源節點到目的節點之間的路徑長度通常隨網絡覆蓋區域的直徑（或面積的平方根）成比例變化，即o(n)。因此，網絡的容量為o(n/n)=o(n)，并且平均每個節點所能獲得的端到端吞吐量滿足o(n/（n×n））。文獻[1]還指出，獲得網絡的最大容量需要節點傳輸半徑等于可保證網絡連通條件下的最小傳輸半徑。

文獻[2]研究了節點傳輸半徑與無線網絡性能之間的關系。該文分析了節點傳輸半徑的變化對源節點和目的節點間跳數以及單個節點可利用帶寬造成的影響，得到了分組無線網絡的節點最優傳輸半徑，即節點的傳輸半徑應使得節點周圍的鄰居節點數為6。這個結論是在節點靜止的網絡場景下分析得到的。文獻[3]將分析擴展到移動無線自組織網絡場景下。仿真表明移動節點所需的最優傳輸半徑要大于靜止網絡中節點所需的傳輸半徑。另外，節點的最優傳輸半徑隨節點移動速度的變化而不同。與文獻[1~3]中分析結果不同的是，文獻[4~6]的分析認為增大節點的傳輸半徑有利于提高網絡的容量，并且當節點的傳輸半徑增大到使網絡拓撲成為全連通結構時，網絡容量達到最大。

影響網絡容量的因素很多，包括路由選路策略、分組調度機制、信道接入控制、業務流特性等。本文主要從信道接入控制層面上來分析節點傳輸半徑對網絡容量的影響。

1 問題描述

本章通過仿真的方法展示節點傳輸半徑不同造成的網絡容量影響。考慮節點數為8的兩個網絡S1和S2，設置不同的節點傳輸半徑使得S1形成一個單跳網絡，而S2成為一個多跳的線性拓撲結構網絡，如圖1所示。仿真采用了NS-2^[7]網絡仿真軟件以及CMU無線擴展模塊^[8]。MAC協議采用了802.11 DCF，并且仿真中所有數據幀的傳輸都基于RTS/CTS模式，信道速率為W=11 Mbps。加載的CBR業務流發生在隨機選取的四對節點上，并且所有業務流的特性一致，分組大小設置為1 020 Byte。

仿真結果如圖2所示。為了方便進行比照，圖2中同時給出了只有兩個節點的網絡中，業務流從一個節點傳輸到另一個節點的情況下網絡容量隨負載的變化關系。從圖2中可以看出，雖然多跳網絡有很高的一跳網絡容量，但是多跳網絡能提供的端到端吞吐量卻遠遠低于一跳網絡。網絡S2中最多可以同時進行的一跳傳輸節點對包括〈1，2〉〈4，5〉和〈7，8〉。網絡S2比S1有更多可以同時進行的一跳傳輸，使得網絡S2的一跳容量遠大于單跳網絡S1。但是，網絡S2中一個業務流分組的傳輸需要消耗更多的中繼節點的傳輸能力，因此導致S2的網絡容量比單跳網絡 S1的容量小。

2 網絡容量分析

假設一個有Ntotal個節點的無線網絡，節點按照均勻分布特性隨機地分布在一個足夠大的區域內，分布密度為λ 。任意時刻節點的發送隊列均不為空，并且節點執行傳輸的概率為P，信道速率為W。如圖 3所示，所有節點傳輸半徑均為R，γMN表示一跳傳輸的兩個節點M與N之間的距離。節點的傳輸覆蓋區域面積為πR2，因此節點傳輸覆蓋范圍內的平均節點數L=λπR2。由于每個節點傳輸覆蓋區域內的鄰居節點數滿足泊松分布特性，該區域內鄰居節點數為n的概率近似為^[2]

prob(n，λπR2)=Ln/n!e-L(1)

任意兩個鄰居節點之間的距離γ的概率密度函數滿足

g(r)=2γ/R2，0≤γ≤R (2)

為分析簡便，本文采用協議干擾模型（protocol interference model）^[1]分析節點間傳輸的互相干擾問題。節點M到N的單向傳輸成功的條件為：a）γMN≤R；b）γKN＞R，K是網絡中任何其他同時進行傳輸的節點并且K≠M，N。另外，由于M在向N發送完數據之后要求N向M發送ACK，因此M與N之間的成功傳輸要求在圖 3所示的陰影區域沒有任何其他節點在同時進行傳輸。陰影部分的面積Sgrey與節點M和N之間的距離有關，即

Sgrey=2πR2(1-f(γMN))(3)

其中：

f(γMN)＝cos-1(γMN/（2R）)/π-(γMN/（2πR)）

1-γMN/（2R）2(4)

節點的一跳傳輸吞吐量有

T1-hop=prob[A1]×prob[A2]×prob[A3]×prob[A4]×kW(5)

其中：k為信道的有效利用率，與協議開銷有關；事件A1表示節點M的傳輸覆蓋范圍內至少有一個節點存在，作為接收節點N，且prob[A1]=1-e-L；事件A2表示節點M發起傳輸，其概率為prob[A2]=p；事件A3表示接收節點N在M傳輸時沒有發起傳輸，概率為prob[A3]=1-p；事件A4表示圖 3中陰影區域沒有其他節點在同時進行傳輸，其概率為

prob[A4]=∫γMN=RγMN=0∞n=2(1-p)n-2prob(n，λSgrey)2 γMN/R2dγMN=∫γMN=RγMN=0∞n=2(1-p)n-2(λSgrey)ne-λSgrey/n!2γMN/R2dγMN=[∫γMN=RγMN=0(∞n=2(1-p)n(λSgrey)n)/n!e-λSgrey2γMN/R2dγMN]/(1-p)2=[∫γMN=RγMN=02[e(1-p)λSgrey-1-λSgrey+pλSgrey]e-λSgreyγMNdγMN]/[(1-p)2R2]

因此，網絡的一跳容量為C′=T1-hop×Ntotal。設所有業務流從源節點到目的節點所經過的平均跳數為H，則網絡的容量為

C=T1-hop×Ntotal/ H(6)

而每個節點所能獲得的端到端吞吐量Tc=C/Ntotal=T1-hop / H。

假設業務流的源節點和目的節點隨機選擇，則源節點i與目的節點j之間的距離dij的概率密度為

p(dij)=dij/∫A0tdt(7)

其中：A為正方形網絡覆蓋區域的面積^[9]。因此，源節點與目的節點之間平均路徑長度為

d=∫A0dijp(dij)ddij=2/3A(8)

同理，由式(2)可得每跳通信的收發節點之間平均距離Dt-r=2R/3。當網絡中節點密度足夠高時，假設從源節點到目的節點的路徑為直線^[9]，則平均跳數有

H=d/Dt-r=(2/3A)/(2/3R)=A/R(9)

由上述分析可知，網絡的容量C與節點的分布密度λ、節點的傳輸半徑R、節點的發送概率p、源與目的節點之間的距離d、網絡節點的數量Ntotal等參數有關。已有文獻表明^[2]，節點的一跳傳輸吞吐量T1-hop在發送概率p=1/λπR2時取得最大值，因此在以下的數值分析中取值p=1/λπR2。

圖4是在單位圓內節點數量為8的節點密度，并且源節點與目的節點之間距離為3個單位長度的條件下，T1-hop和Tc 隨節點傳輸半徑R變化關系的數值分析結果。可以發現，隨著R的不斷增大，T1-hop在達到最大值后將急劇下降。而此時Tc也隨之下降，盡管增大傳輸半徑使得源節點與目的節點之間所需的轉發跳數減少了。其原因在于，隨著R的增大，節點的一跳鄰居節點的數量將呈平方關系增長，則每個節點所能獲得的信道傳輸能力將按平方關系下降。而源節點與目的節點之間的路徑跳數卻只隨R的增長呈線性下降。這使得前者的變化速率超過了后者，所以超過一定范圍的傳輸半徑的繼續增加反而會導致網絡容量下降。

本文通過假定所有業務流從源到目的節點的距離為dij=d，來考察怎樣的情況下多跳傳輸的網絡容量可以比單跳傳輸的容量高，即

T1-hop×Ntotal×Dt-r/d≥kW(10)

式(10)代入T1-hop和Dt-r，并將傳輸半徑R取值為使得網絡容量達到最大的值，于是可以得到Ntotal與d之間的關系，如圖5所示。分界線表示Ntotal與d之間呈線性變化關系，當（d，Ntotal）位于分界線上方，多跳傳輸比單跳傳輸獲得的網絡容量大；當（d，Ntotal）位于分界線下方，單跳傳輸可以比多跳傳輸獲得更大的網絡容量。

3 仿真分析

3.1 仿真模型

多跳無線網絡節點之間傳輸的相互干擾以及隱藏終端的存在，使得精確建模分析非常困難^[10，11]。為此，本文采用仿真的方法作進一步分析。為了便于在仿真中控制業務流的路徑跳數，本文采用了正方形的格形拓撲結構網絡進行仿真分析。在仿真過程中，節點位置保持不變，并且網絡中所有節點的傳輸半徑均相同，相鄰節點在水平和垂直方向上的距離都設定為單位長度。業務流的源節點和目的節點隨機地在同一水平直線或同一垂直直線上選取，并保證所有業務流源節點到目的節點的距離都相等，以考察不同傳輸路徑長度的情況下，節點傳輸半徑對網絡容量的影響。業務流類型采用CBR，分組大小設置為1 020 Byte，業務流傳送的仿真時間為300 s，信道速率為11 Mbps， MAC協議仍采用IEEE 802.11 DCF機制（RTS/CTS模式）。

由于路由協議報文的傳輸會帶來一定的網絡開銷，筆者對DSDV路由協議進行簡單改造。仿真過程中，節點首先通過DSDV路由協議形成到達網絡中其他節點的路由；然后將路由表固定，并停止DSDV路由協議的運行；接下來再加載網絡業務流，這樣避免了路由開銷對業務流傳輸的影響。

為了保證不同業務流之間以及同一業務流的各跳傳輸之間的公平性^[9]，本文采用了如下機制：a）節點在轉發每個流的分組時，確保下一跳節點的緩存隊列中屬于此業務流的待發送分組數目不多于10個，否則在本節點緩存這個分組等待發送；b）源節點產生的分組在待發送隊列中的數目不超過10個，否則丟棄；c）節點以WFQ(weight fair queueing)方式對隊列中多個業務流的分組進行調度發送。這樣，每個流的分組均能盡可能地被投遞至目的節點，不同流也能夠在一定程度上公平共享每個中繼節點的傳輸帶寬。

3.2 仿真結果

圖6(a)給出了7×7節點的格形網絡的網絡容量隨節點傳輸半徑變化的關系曲線。其中不同的曲線表示加載不同傳輸距離的業務流情況下的仿真結果。當業務流的源與目的節點之間距離小于三個單位長度時，節點傳輸半徑的增長造成網絡容量下降；而當業務流的源與目的節點之間距離大于三個單位長度時，傳輸半徑的增長卻使得網絡容量上升。網絡容量隨傳輸半徑的增長而增長這一仿真結果與文獻[4~6]中的研究結論相符，卻與本文理論分析的結果相悖。其原因在于，本文進行理論分析時沒有考慮網絡的邊際效應和隱藏終端問題造成的影響。處于網絡邊緣的節點面臨的信道競爭較少，更容易競爭獲得信道，使得經過這些節點的業務流有較高的吞吐量；而多跳網絡中的隱藏終端問題將嚴重降低網絡的吞吐量^[10]。

為了減小仿真中網絡邊際效應給仿真結果帶來的影響，筆者將仿真的網絡規模擴大，保證所有被考察節點到網絡邊緣的距離大于節點傳輸半徑的兩倍。這樣，當節點傳輸半徑是一個單位長度時，如果仿真分析7×7節點的格形網絡，則實際仿真網絡將擴展為13×13節點的格形網絡。另外，網絡加載的業務流分兩部分，一部分只與被考察節點有關，源節點、目的節點以及所有中繼節點均是被考察節點；另一部分只與被考察節點以外的其他節點有關。圖6(b)給出了擴大仿真網絡規模后的仿真結果。從圖中可以看出，隨著節點傳輸半徑的增大，不管業務流的源節點與目的節點之間距離如何，網絡容量均呈下降趨勢，這個與前面的理論分析結果一致。

筆者通過仿真發現了與文獻[4~6]結論不同的結果，即網絡容量并不一定隨著傳輸半徑的增大而增長。實際上，網絡容量除了受傳輸半徑變化的影響，還與業務流的源和目的節點之間的距離以及整個網絡的節點數量有關。圖7給出了9×9節點的格形網絡的仿真結果。對比圖6(a)和圖7(a)可以發現，當9×9節點網絡的節點傳輸半徑增大，網絡容量也隨之增大時，業務流的源節點和目的節點之間的距離要比相應的7×7節點網絡中的要大。這是因為，在網絡節點的分布密度保持一定的情況下，網絡節點數量的增多會造成網絡的覆蓋范圍增大，從而使信道的空間重用次數得到提高，網絡中可以有更多的一跳傳輸同時進行，網絡一跳容量增大。

圖8給出了節點傳輸半徑為一個單位長度的情況下，網絡容量隨業務流的源節點與目的節點之間距離的變化關系曲線。可以看出，多跳傳輸的網絡容量與單跳傳輸的網絡容量的大小關系，不僅與網絡中節點的數量有關，而且與網絡中業務流的源節點和目的節點間距離有關。網絡中節點數量越多，出現多跳傳輸的網絡容量小于單跳傳輸的網絡容量時，網絡所能容忍的業務流源節點和目的節點之間的距離越大。明確這一變化關系，有利于在對一定數量的網絡節點組網的過程中，考慮是組建多跳網絡還是單跳網絡，以獲得更大的網絡容量。

4 結束語

本文對無線自組織網絡中節點傳輸半徑給網絡容量帶來的影響進行了研究。理論分析表明，隨著節點傳輸半徑的增長，節點的一跳鄰居節點數量呈平方關系增長，由此每個節點所能獲得的信道傳輸能力呈平方關系下降。而業務流的源節點和目的節點間的中繼跳數只隨傳輸半徑的增長線性下降，因此網絡容量將隨節點傳輸半徑的增長而減少。網絡的容量不僅與節點傳輸半徑有關，而且還與業務流傳輸的路徑長度和網絡的節點數量有關。在實際的多跳無線網絡中，由于隱藏終端問題的存在，增加節點的傳輸半徑可能導致網絡容量的增加，也可能減小，受業務流的傳輸路徑長度和網絡節點數量的影響。當然，網絡容量還與網絡的拓撲結構、采用的MAC協議以及路由協議等因素有關，筆者將在今后作進一步的研究。

參考文獻：

[1]GUPTA P， KUMAR P R. The capacity of wireless network[J]. IEEE Trans on Information Theory， 2000， 46(2):388-404.

[2]KLEINROCK L， SILVESTER J. Optimum transmission radii for packet radio networks or why six is a magic number[C]//Proc ofIEEE National Telecommunications Conference. Birmingham: IEEE， 1978.

[3]ROYER E M， MELLIAR P M， MOSER L E. An analysis of the optimum node density for Ad hoc mobile networks[C]//Proc ofIEEE International Conference on Communications. Helsink: IEEE， 2001.

[4]BEHZAD A， RUBIN I. High transmission power increase the capacity of Ad hoc wireless networks[J]. IEEE Trans on Wireless Communications，2006，5(1):156-165.

[5]DUTKIEWICZ E. Impact of transmit range on throughput performance in mobile Ad hoc networks[C]//Proc of IEEE International Confe-rence on Communications. Helsink: IEEE， 2001.

[6]NILSSON A. Performance analysis of traffic load and node density in Ad hoc networks[C]//Proc of European Wireless. Barcelona:[s.n.]，2004.

[7]VINT Group. UCB/LBNL/VINT Network simulator(NS)，version 2[DB/OL]. http://www.isi.edu/nsnam-/ns/.

[8]CMU Monarch Group. CMU Monarch extension to NS[EB/OL]. http://www.monarch.cs.cmu.edu.

[9]LI J， BLAKE C. Capacity of Ad hoc wireless networks[C]//Proc of the 7th Annual International Conference on Mobile Computing and Networking. Rome: ACM SIGMOBILE， 2001.

[10]HE J， PUNG H K. Performance modeling and evaluation of IEEE 802.11 distributed coordination function in multi-hop wireless networks[J].Computer Communications，2006，26(9):1300-1308.

[11]GAO Y， CHIU D M， LUI J C S. Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications[C]//Proc of Joint International Conference on Measurement and Modeling of Computer Systems. New York: Association for Computing Machinery， 2006.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文