基于連通概率的Mesh網關節點選擇

程志強

（武漢船舶職業技術學院公共課部，湖北武漢 430050）

無線網狀網能為臨時會議、礦井、災后救援等場合下的實時Internet接入提供有效的平臺。當網絡規模較大時，多采用多網關方案接入Internet，提供性能提升，但也會帶來更大的建設與維護成本，簡單的增加網關節點不一定意味著網絡性能與網關數目按正比例提升；網關的布設位置也會影響到路由和網絡性能，需要采用最有效的策略和方式來布設有限的網關。

目前針對 WMN中Internet網關（IGW）選擇方案的研究，其優化目標包括最小化所布設的網關數目、最小化通信時延（跳數）［1，2］、負載均衡［3，4］、最大化吞吐量［5，6］等，需滿足的約束條件通常為跳數、負載、簇大小、吞吐量等Qos參數。很少有研究考慮到了無線信道質量（鏈路失效和拓撲變化頻繁）對通信的影響，當拓撲發生改變時，給出的方案就不見得是最佳的。基于無線信道質量的網關選擇方法［7］與本文的思路最為接近，以Mesh節點到其所屬網關的傳輸成功率作為約束條件，保證整個網絡的信道利用率，同時降低從Mesh節點到網關的平均傳輸時延，從而優化網絡吞吐量。但研究中假設雙向的鏈路為同質的，不符合實際無線信道雙向傳輸特性不對稱的情況，且這種方案并未采取全局優化策略，不能夠保證網絡中Mesh節點到網關的總體傳輸成功率最高。

針對無線鏈路容易出現失效、網絡出現分割的特點，本文基于無線鏈路可用概率，設計對WMN進行子網劃分，并在各子網內選擇最佳網關節點的方法，使每個子網內部具有較高的連通性，各個節點連通到網關的概率最高，而鏈路失效和網絡拓撲變化對網絡性能的影響最小。

1 網關節點的選擇思路

網關布設問題描述如下：給定物理網絡拓撲，在網絡中選擇網關的數目和位置，使得性能需求得到滿足，且布設和維護的代價最小。無線鏈路失效頻繁，容易產生網絡分割，本文將網絡自然分割后得到的結果作為子網劃分的參照依據，所采用的方法包括2個步驟：

首先是網絡劃分：根據網絡中各鏈路失效的概率，找出最可能出現的網絡分割情況，據此劃分子網，使每個子網內具有較高的穩定性和連通性，而相鄰子網間的鏈路為具有較低穩定度的邊割集。

然后是網關選擇：依據鏈路的穩定性，在各個子網內選擇最佳的節點（集）作為該子網中的網關，使得網關節點能在該子網內提供最大可靠度的服務，使各個節點連通到Internet的概率最高，而鏈路失效和網絡拓撲變化對系統服務的影響最小。

2 子網劃分方案

2.1 網絡分割概率

設網絡中鏈路數目為｜E｜，進行無線鏈路質量測量的總時間長度為T（大約為幾十個小時），將T劃分為N 個slot，每個slot的時間長度為t0（大約為幾秒），為無線鏈路質量統計的時間粒度，每個slot中可采集到若干個鏈路質量指標數據。計算在［j＊t0，（j＋1）＊t0］時段內，鏈路Li的質量測度指標（如PDR）的數學期望E（Rij）和方差D（Rij），這樣得到各個鏈路在N個slot中的鏈路質量指標的數字特征。

取數學期望的閾值Eth和方差的閾值Dth，若E（Rij）大于Eth，且D（Rij）小于Dth，則此鏈路Li在時段j內被認為沒有失效，否則被認為是失效的。將具體的質量指標統計值轉換為統一的布爾類型數據，對每條鏈路Li生成鏈路狀態N元組Ai＝ ｛ai1，ai2，…aiN｝，如果對應第j個slot時鏈路沒有失效，則aij＝1，否則aij＝0。對鏈路Li而言，在整個測量時間段內的鏈路失效概率為：

網絡出現分割分為2種情況：節點無法向外發送數據，和節點無法從外接收數據。求解某個邊割集中的邊同時失效的概率，即為網絡分割產生的概率，相關定義如下：

［定義1］外向邊割集

給定有向圖G（V，E）中的連通點集S，從S到V－S的有向邊形成一個外向邊割集合｛e1，e2，…，es｝，記為S的外向邊割集ECO（S）。

表示長時期內子網的各條外向割邊同時失效、該子網成為向外不連通子圖的概率，體現了子網內的節點訪問子網外的網關的可靠程度。

［定義2］內向邊割集

給定有向圖G（V，E）中的連通點集S，從VS到S 的有向邊形成一個內向邊割集合｛e′1，e′2，…，e′t｝，記為S的內向邊割集ECI（S）。

表示長時期內子網的各條內向割邊同時失效、該子網成為向內不連通子圖的概率，體現了子網外的節點訪問子網內的網關的可靠程度。

如果一條邊的失效概率較低，那么包含這條邊的邊割集使得網絡發生分割的概率就較低，因此可以設定一個邊失效概率閾值PEth，在分析時排除失效概率較低的邊以及含這些邊的邊割集。如果內向邊割集或外向邊割集中的邊全部失效，則連通點集S與V－S不連通，出現了網絡分割事件F（S），對應的網絡分割概率為

對劃分的子網可進行如下的分類：

［定義3］主連通子網

如果將點集S從G中分割開來需要多個割集，則該點集及點集內節點的所有邊構成主連通子網。

［定義4］端連通子網

如果將點集S從G中分割開來只需要一個割集，則該點集及點集內節點的所有邊構成端連通子網。

2.2 子網劃分方法

基于以上的分割模型，所采取的子網劃分方法是：給定圖G（V，E）和網關的最大數目L，選擇K－1個邊割集ECm，1≤m≤K－1，將網絡分為K個子網，使得V＝｛C1∪C2∪…CK｝，Ci∩Cj＝Φ，1≤i，j≤K，K≤L，得到1個主連通子網和K－1個端連通子網。將子網劃分問題表示為整數線性規劃（ILP）模型如下：

式（5）所示的第一優化目標為選擇網絡分割概率最大的邊割集，體現最可能出現的網絡分割，式（6）所示的第二優化目標為找出盡可能多的端連通子網，即網絡分割不連通的可能情況；式（7）所示的約束條件表示每個子網中的節點數Numi不能小于下限MinSize，以保證子網的最小規模，式（8）所示的約束條件表示依據子網中的節點數分配合適的網關數目NGi，滿足每個網關最多為MaxSize個節點提供服務，達到合理的負載分布，式（9）所示的約束條件表示網絡中的實際網關總數不能大于預定的數目L。

2.3 關節點選擇方法

在相對穩定的子網中，首先排除明顯不合適作為網關的節點（如鏈路有效概率低的節點、度數為1的節點），找出子網內滿足條件的候選網關節點組合，計算子網中其它節點向候選節點（組）通信的可靠度，選擇具有最高可靠度的節點（組）作為網關。傳統的通信可靠度計算方法［8］基于兩點間所有的路徑計算連通的成功概率，如果經過多條路由的多次嘗試最終連通成功，也認為兩點之間是可靠的，這樣計算得到一個很接近1的概率值，這種方式著眼于連通的“可能性”，而沒有考慮通信的“時效性”，沒有實用參考價值。從通信實時性的角度，選擇具有最大可靠度的1條路徑計算可靠度。

［定義5］1次2－終端可靠度Rel1（s，T）

給定從源點s到匯點集合T的所有路徑，選擇可靠度最高的一條路徑用于通信，該路徑的可靠度即為s到T的1次2－終端可靠度，體現首次嘗試即可連接成功到某一個網關的概率。

其計算方法為：設從T外的節點vp到T中的節點vq的某條路徑P中含鏈路L1，L2，…LQ，路徑中不包含其它的匯點。給定鏈路狀態N元組，路徑P在時段j可用則意味著其中的各條鏈路在時段j都有效，因此路徑有效的長期統計概率為

選出具有最高可靠度的一條路徑，其可靠度值即為從節點vp到vq的1次2－終端可靠度Rel1（vp，vq），求出節點vp到T的1次2－終端可靠度為

本文開發出一種遍歷算法，計算子網內所有其它節點到候選組合節點的1次2－終端可靠度總和，選擇可靠度總和最大的一個組合作為網關節點集合。算法描述如下：

Input：W 個候選網關節點，網關數目SK，各有向邊的狀態N元，

Output：所選的SK個網關節點

步驟：

（1）可能的網關節點組合有CSKW個，取出這些組合。

（2）對每個組合中的節點集Ti，求S－Ti中的每個節點vp到Ti中每個節點vq的路徑集合，基于各邊的狀態N元組，求各路徑的長期統計有效概率。

（3）對S－Ti中的節點vp，求其到Ti中的節點的1次2－終端可靠度的最大值，記為Rel1（vp，T）。

3 仿真實驗與性能評價

3.1 比較方案和性能指標選擇

傳統的網關選擇多基于Qos參數指標，典型的包括基于跳數的選擇方案（Sel－DI）和基于節點度數（最大化吞吐量）的選擇方案（Sel－DE）。將本文提出的基于可靠度的網關選擇方案（Sel－RE）與傳統的網關選擇方法進行比較，其中三種方案都限定相同的網關最大數目。所用的性能指標為：1）體現分組發送成功率的分組抵達率（PDR）；2）體現分組傳輸速度的平均端到端時延（Delay）；3）體現負載均衡程度的歸一化負載的標準差（LoadStDev）——在網絡中，K 個網關分攤所有接收到的服務請求數據包，給定網絡中服務請求總數Qt和網關Si所處理的請求數Q（Si），歸一化Si所處理的請求占比為αi＝ Q（Si）／Qt，求出這些比例的標準差為

3.2 仿真實驗網絡設置

實驗仿真拓撲如圖1，含18個節點和23條無線鏈路（用虛線表示）。鏈路的失效概率在直觀上可用鏈路中定長的信令數據包的丟包率來體現，可認為無線鏈路上的丟包率pi正比于對應入邊（incoming edge）的失效概率，為了簡便起見，不考慮鏈路失效概率及丟包率的時變性。因為含有更多無線接口的節點會受到更嚴重的信道干擾和信道失效，因此度數高的頂點會具有相對較高的pi。如表1所示，設置了7個邊失效實例（記為EII－x），在不同的邊失效實例中對不同的頂點度數設置了不同的pi。較大的頂點度數對應具有較高的pi，對給定的頂點度數，從EII－1到 EII－7時pi不斷增大。

圖1 仿真拓撲示例

表1 入邊對應的丟包概率（pi）

基于NS－2仿真軟件，在無線物理層代碼的數據包接收函數中添加代碼，實現特定的鏈路按預定概率隨機丟包的模型，體現鏈路的隨機失效效果。基于不同的參數，包括預定的網關數目（K＝2，3）、邊失效實例（EII－1到 EII－7）和三種網關選擇方案，設置不同的仿真場景。在每個場景中，仿真持續60秒，每個MR節點以100包／秒的速率，根據AODV所選的路由向對應的網關發送CBR數據包。

3.3 仿真實驗結果與分析

關于分組抵達率PDR的結果如圖2、圖3所示。可以看出，Sel－RE方案考慮到了全網無線鏈路的可靠程度，故能提供最高的PDR，Sel－DI方案以網絡的拓撲和節點間物理距離為參照依據，其PDR次之，Sel－DE方案從單個節點能力的角度、而未從全網的角度考慮網關選擇問題，其PDR最低；在各個方案中，采用3個網關時的PDR要明顯高于2個網關的情況；隨著鏈路失效概率的增大，各方案下的PDR都將降低。

關于平均端到端時延Delay的結果如圖4所示。從結果中看出，在K＝2與K＝3時，Sel－RE方案都具有最小的Delay，Sel－DE方案和Sel－DI方案的Delay較大。其原因在于Sel－RE方案考慮到了高度數（較多無線接口）的節點上的信道干擾和排隊時延等影響因素，能避免選擇性能瓶頸節點作為網關。在各個方案中，當采用更多的網關時，能實現更小的Delay，故K＝3時的時延要明顯小于K＝2時的。

圖2 各網關選擇方案的分組抵達率（K＝2）

圖3 各網關選擇方案的分組抵達率（K＝3）

圖4 各網關選擇方案的平均端到端時延（K＝2，3）

圖5 各網關選擇方案的歸一化負載標準差（K＝2，3）

關于歸一化負載標準差LoadStDev的結果如圖5所示。可以看出，無論是K＝2還是K＝3時，Sel－RE方案和Sel－DI方案的LoadStDev都較小，而Sel－DE方案中的流量集中于高度數節點，未考慮實際的拓撲和流量分布，故容易造成負載不均衡的情況，其LoadStDev明顯較大。

4 結 語

本文提出的方法在惡劣通信環境中具有實時性和高效性。給定網關數目，本文的方法可用于以最高連通概率布設網關，給定最小網絡分割概率，本文的方法可用于確定所需的網關數目。進一步的工作包括設計動態網關切換策略，以應對某個網關失效的情況。

1 He，B.，Xie，B.，Agrawal，D.P.：Optimizing deployment of Internet gateway in Wireless Mesh Networks.Computer Communications.31（7），1259－1275（2008）

2 Li，T.S.，Luo，J.Y.，Ge，Z.H.：Gateway deployment algorithm based on voronoi diagrams in wireless mesh networks.Journal of Southeast University（Natural Science Edition）.40（supII），328－332（2010）

3 Wu，W.J.，Luo，J.Z.，Yang，M.：Gateway Placement Optimization for Load Balancing in Wireless Mesh Networks.In：13th International Conference on Computer Supported Cooperative Work in Design，pp.408－413.IEEE CS Press，New Jersey（2009）

4 Feng，Z.，Chen，Z.G.：.Load Balancing Placement of Gateways in Wireless Mesh Networks with QoS Constraints.In：9th International Conference for Young Computer Scientists，pp.445－450.IEEE CS Press，New Jersey（2008）

5 Xin，Q.，Wang，Y.J.：Gateway Selection Scheme for Throughput Optimization in Multi－radio Multi－channel Wireless Mesh Networks.In：5th International Conference on Mobile Ad－hoc and Sensor Networks，pp.187－195.IEEE CS Press，New Jersey（2009）

6 Ahuja，S.，Krunz，M.：Algorithms for server placement in multiple－description－based media streaming.IEEE Transactions on Multimedia.10（7），1382－1392（2008）

7 Zhou，N.，Zeng，Z.W.，Chen，Z.G.：Gateway Placement Algorithm Based on Transmission Success Rate in Wireless Mesh Network.Computer Engineering.36（12），110－112（2010）

8 Egeland，G.，Engelstad，P.E.：The Availability and Reliability of Wireless Multi－Hop Networks with Stochastic Link Failures.IEEE J.SAC.27（7），1132－1146（2009）