無線Mesh網絡結構的拓撲控制策略

鄧建良，王 景，胡松華，郭建丁

（重慶大學通信工程學院，重慶400044）

0 引言

拓撲控制機制從研究方向可歸納為節點功率控制和層次型拓撲結構組織兩類。無線網絡中的層次型拓撲結構由于具有通信量少、可擴展性強、能量利用效率高及適合大規模部署等特點，成為當前拓撲控制研究的重點。

提出一種新的網絡架構并在此基礎上研究一種虛擬的層次化拓撲控制策略，主要考慮相鄰簇間的自身負載和相互轉發負載的平衡，提高網絡的公平性、提升鏈路可靠性以及提高路由算法的有效性。

1 問題說明

該文研究的前提是，無線Mesh網絡的簇都分配了足夠等量的信道資源，從而保障通信的公平性和鏈路的可靠性。在一定節點分布的情況下，節點不但自身通信產生負載，而且節點同時要轉發產生負載。圖1中，簇1和簇4僅僅只是簇內節點間通信和與內外簇間的通信。而簇2和簇3不僅要承擔自身通信與簇間通信，還要轉發簇間的通信。簇2和簇3的通信負載相對大很多，網絡中處于中間轉發位置的節點承擔相對較多的負載，缺乏公平性。同時網絡的容量和可靠性依賴于中間位置的簇。

圖1 簇的通信狀況

新的劃分簇的方法主要從2個方面來分析:覆蓋范圍和容量。其次簇大小的劃分也必須考慮信道資源的分配，盡量使其每個虛擬簇內的節點都滿足信道匹配。必須要強調的是網絡考慮覆蓋范圍，同時要達到公平性的網絡基本要求。

根據新的網絡架構—虛擬層次無線Mesh網絡結構，提出一種拓撲控制策略，拓撲控制策略主要應用于簇間的控制。在極值情況下，其拓撲控制能量域為。在圖2中，一個點代表一個簇。這是一個由7個簇組成的鏈型拓撲。在這種情形下，每個簇僅僅為相鄰節點轉發數據報和發送自身與其他節點的通信數據。簇1和簇7與其他簇的通信都經過其相鄰簇轉發，而其本身僅僅承擔簇內部通信和與相鄰簇的通信。n為網絡某一側中虛擬簇的數量;H（d）為虛擬節點ci與ci-1之間的鏈路容量;li為節點虛擬簇半徑;R（li）為li內部流量負載其中RD是指每個用戶內部平均流量，DM指節點密度虛擬簇2個簇間流量負載其中RZ是指每個用戶內部平均流量，DM指節點密度;虛擬簇中所有的流量負載應該受到蜂窩飽和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示飽和吞吐率。根據文獻[4]中的方法，對于用戶數量k，IEEE 802.11 b WLAN的單元飽和吞吐量可以使用曲線擬合的方法獲得，即則簇2轉發的流量是簇3轉發流量是簇4轉發流量是在等半徑的情況下，內部流量負載和虛擬簇間流量負載是相等的。所以簇2的轉發流量為5R（lin），簇3轉發流量為8R（lin），簇4的轉發流量為9R（lin）.

圖2 簇數目為7的鏈型拓撲和轉發流量圖

可以很明顯看出簇的流量負載是不均衡的，網絡的性能將受到中間簇的限制。所以該文提出一種新的簇劃分方法，根據其總的流量來改變簇的覆蓋范圍，達到簇間流量和轉發流量之和在每個簇中都是相等的。由此其簇的劃分為圖3所示。

圖3 負載均衡簇的分配方式

將轉發流量大簇縮小其覆蓋范圍，保障簇內部節點能夠正常通信，從而保障通信的可靠性和公平性。它們覆蓋半徑之間關系是:

以2種簇拓撲進行研究，圖4和圖5分別是虛擬簇半徑相等和虛擬簇半徑逐漸增大的拓撲，為便于分析，用位于小區中心的虛擬節點表示每個小區，實際上節點可位于小區內任何位置。為了用連接圖來表示這種虛擬層次網絡結構的拓撲，鄰居虛擬節點用一條邊連接，均給出了對應的Mesh網絡拓撲結構。

圖4 虛擬簇半徑相等的拓撲形式

圖5 虛擬簇逐漸增大的拓撲形式

從組合圖論的角度，可以知道簇半徑相等和簇半徑逐漸增大拓撲在等分帶寬上是相同的，所考慮的是鏈路的等分帶寬，但是，如果考慮信道資源分配，虛擬簇中節點有些鏈路不是活躍的;如果考慮鏈路的活躍性，則可以知道簇半徑逐漸增大的拓撲在等分帶寬性能上優于等半徑拓撲，因為在理想情況下，簇半徑逐漸增大的拓撲可以是信道資源分配和簇節點完全匹配。

2 算法規則

在圖3中，由于簇的劃分是對稱的，考慮其中的上半部分，定義一些參數:n為網絡某一側中虛擬簇的數量;di為小區中心的虛擬節點ci于ci-1之間的距離;H（di）是虛擬節點ci與ci-1之間在間距為di情況下的鏈路容量;li為節點ci的蜂窩半徑;R（li）為到達ci的流量負載，其中RD是指每個用戶平均流量，DM指節點密度;δ（n）為代價函數，指部署一個虛擬簇所需代價;R（s）是指從其他虛擬簇接收到的流量與本簇轉發出流量差值。

接下來，介紹2種虛擬簇劃分策略:等半徑虛擬簇的劃分和半徑逐漸增大的劃分策略。2個虛擬中心節點的間距可以描述如下:di=li+li+1，i=1，2，…，n。虛擬簇中所有的流量負載應該受到蜂窩飽和吞吐率的限制，即:R（li）≤Rb（k），其中，Rb（k）表示飽和吞吐率。根據文獻[3]中的方法，對于用戶數量k，IEEE 802.11b WLAN的單元飽和吞吐量可以使用曲線擬合的方法獲得，即:Rb（k）=b1eb3k+b2eb4k。故虛擬簇的總流量為

等半徑情況下:

半徑逐漸增大情況下:

在該網絡中，虛擬簇的劃分問題可以描述成一個混合整數非線性編程（MINLP）問題，其中決策變量包括n和l0，l1，…，ln。MINLP問題的目標是使虛擬簇的總體負載流量與劃分簇的代價函數比值達到最大化。于是有目標函數:

對于等半徑情況下有目標函數:

半徑逐漸增大情況下有目標函數:

算法流程如圖6所示。

定理1:任何滿足簇的域內連通性和互通性的模型，必定具有拓撲連通性。

證明:?u，u′∈V，假定u∈Vi，u′∈Vj，因拓撲具有簇的域內連通性和互通性，則u和u′之間一定存在一條路徑（u，ci，…，ck，cm，…，cj，u′）。

定理2:當d滿足時，拓撲內簇群必定滿足域內連通性和簇間鄰接可達性。

圖6 算法流程

證明:由簇滿足域內連通性則必有d≤dmax。假定簇Cj具有最大規模d，且d（k，m）=d，其中k，m∈Vj，因此可知簇Cj內其他節點必位于圖所示區域akcm內，為滿足簇間鄰接可達性，若節點a與b可直接通信，必能保證相鄰簇區域內任意2節點可直接通信，由圖易得簇群必定滿足域內連通性和簇間鄰接可達性，證畢。

圖7 簇規模與簇區域關系圖

3 結束語

從拓撲控制出發，探討一種能夠增大網絡容量且保證網絡可靠性的拓撲結構。通過對隨機拓撲和2種規則拓撲的網絡容量和拓撲特征分析，表明了規則拓撲在無線Mesh網絡應有的優良性能。該文提出的方案對現有無線Mesh網絡結構改動較小，主要工作是在網絡幀結構中添加虛擬分簇標志和組網拓撲方式等調整，易于工程實現。

[1]SANTI P.Silence is golden with high probability:Maintaining a connected backbone in wireless sensor networks[C]//1st European Workshopon WirelessSensor Network，2004，2（9）:9-20.

[2]XIONG Shu-ming，WANG Liang-Min，WU Ji-Ying.Energyefficient hierarchical topology control in wireless sensor networks using time slots[C]//Proceedings of the Seventh International Conference on Machine Learning and Cybernetics，Kunming，12-15 July 2008:33-39.

[3]徐俊明.組合網絡理論[M].北京:科學技術出版社，2005.

[4]PERILLO M，ZHAO C，HEINZELMAN W.On the problem of unbalanced load distribution in wireless sensor networks[C]//Proceedings of the IEEE Global Telecommunications Conference Workshops.Piscataway，NJ，USA:IEEE，2004:74-79.

[5]CHEN J C.Measured performance of 5GHz 802.11a wireless LAN systems[S].White Paper of Atheros Communications，2001.8.

[6]GUPTA P，KUMAR P R.Thecapacityofwireless networks[J].IEEE Trans.Inform.Theory，2000，46（2）:388-404.

[7]TOUMPIS S，GOLDSMITH A J.Capacity regions for wireless ad hocnetworks[J].IEEE Transactions on Wireless Communications，2003，2（4）:736-748.

[8]SILVESTER J，KLEINROCK L.On the capacity of multichip slotted ALOHA networks with regular structure[J].IEEE Trans.Commun.，1983，31（8）:974-982.