無線光通信網絡拓撲形成問題研究?

程 樸 覃慧玲

（1.華中光電技術研究所-武漢光電國家實驗室 武漢 430223）（2.中國船舶重工集團公司第七二二研究所 武漢 430223）

1 引言

無線光通信［1］是以激光為載體來傳遞信息的一種通信方式。無線光通信網絡是無線光通信與移動自組織網絡相結合的產物。無線光通信網絡具有無中心、自組織、可快速展開、可移動和多跳等特點，它通過多跳數據的傳遞能夠繞開各種障礙物，實現遠距離的跨節點通信，拓展了無線光通信的作用距離和覆蓋范圍；它通過無中心分布式對等網絡［2］的組成，實現了各通信節點的自組織功能，有效降低了局部鏈路失效帶來的全局癱瘓風險，提高了網絡的健壯性和靈活性。

無線光通信網絡初始化過程中，一個通信節點面臨著多個候選通信對象，而節點內通信收發機的數量又是有限的（即節點的度），因此，需要獲得一種拓撲形成（拓撲控制）算法來實現通信鏈路的優化選擇，以期形成連通的最優網絡拓撲結構。目前，國內外已有一些針對無線光通信網絡拓撲結構方面的研究［3］。拓撲控制主要是利用Heuristic方法［4］計算一種最優的拓撲，使得物理層的誤碼率與網絡層的擁塞率都達到最小；文獻［5］中，主要是針對無線光通信網絡中環形拓撲的控制進行研究。文獻［6］研究FSO的重點是通過控制網絡擁塞最小的拓撲結構來實現動態重構。文獻［7］中提出了一種新的分組無線網絡拓撲控制（NTC）的算法，以實現高吞吐量的連接。本文主要以無線光通信網絡樹形結構為對象，將網絡的拓撲形成問題轉換為度約束最小生成樹（DCMST）問題，并引入了一種快速近似算法來加以求解。

2 問題描述

無線光通信網絡的拓撲形成的目的是優化選擇網絡中各節點的通信對象，建立節點間的通信傳輸路徑，實現網絡各節點的互連互通。結合圖論理論，可以將無線光通信網絡用圖論的方式加以表達。由于無線光通信網絡點對點間的通信鏈路往往是雙向的傳輸的，因此無線光通信網絡的連通圖可以當作無向圖［8］

G=(V,E,W)，其中，V={1,2,…,n}為頂點集，代表無線光通信網絡中節點的集合；E為邊集，代表各通信節點間潛在鏈路的集合；W=(wij)n×n為權矩陣，且wij=wji，wii=+∞，代表通信傳輸代價，可用通信距離、延時、誤碼率等參數來衡量；各頂點的度約束設為bi{i=1,2,…,n}，代表節點i內通信收發機的數目。

圖論中，無圈的連通圖稱為樹。如果存在子圖T包含G中所有頂點和一部分邊，且不形成回路，則稱T為圖G的生成樹。代價最小的生成樹則稱為最小生成樹（MST）。當節點度受限時，這種帶有頂點度約束的最小生成樹問題被稱之為度約束最小生成樹（DCMST）問題。因此，無線光通信網絡節點通信收發機數量受限的情況下，其最優拓撲的形成問題就轉化為圖G度約束最小生成樹的問題，其數學模型可表述如下：

這里，變量集合S中所含圖G的頂點個數，約束（2）、（3）保證了所求得的為棵生成樹，約束（4）為度約束。

3 算法的實現

就一般情形而言，度約束最小生成樹的問題是一個NP完備的難解問題，曾經出現過的一些精確算法（如分支定界法等［9］）都是指數時間的，無法求解中型以上規模的實際問題［10］。本文這里引入了一種快速近似算法，經證明其計算時間復雜度為O(n2log2n2)，可對一般意義下的DCMST問題進行求解［11］。

針對模型，該快速近似算法的其核心是，在不違反度約束和不形成圈的前提下，每次加入權最小的邊，直至加入n-1條邊為止。該算法的具體步驟如下：

1）G的邊權矩陣（第i列表示圖G的第i條邊，的第i列的前兩行儲存第i條邊關聯的頂點編號，第3行儲存第i條邊的權），對邊權矩陣按照邊的權進行從小到大排序，設排序后的矩陣為BW。

2）由各頂點的度約束bi(i=1,2…,n)，生成各頂點的初始度檢查值di=bi(i=1,2…,n)。

3）將BW中具有最小權的邊（為BW的第一列）及該邊所關聯的頂點（不妨設該邊所關聯的頂點為i1和j1）加入到圖T中，修改這兩個頂點度的檢查值：將和對應的度檢查值減去1（即：，并從BW中刪除該邊更新BW。

4）檢查BW的第1列對應的邊是否可以用：如果該邊所關聯的頂點的度檢查值都大于0，而且將該邊加入到圖T后，圖不會形成圈，則BW的第1列對應的邊可以用，否則該邊不可以用，從BW中刪除該邊，更新BW，直到BW的第1列對應的邊可以用為止。轉入步驟5）。

5）檢查圖中邊的數目是否小于n-1，如果圖中邊的數目不小于n-1，則已經找到一棵近似度約束最小生成樹，轉步驟6）；否則將BW中具有最小權的邊（為BW的第一列）及該邊所關聯的頂點加入到圖中，并將該邊所關聯的頂點（不妨設該邊所關聯的頂點為ik和jk），所對應的度檢查值減去1（即：，并從BW中刪除該邊更新BW，轉步驟4）。

計算圖的總權重，輸出圖及總權重。

圖1 無線光通信網絡示意圖

4 計算機仿真

假設存在如下圖所示的無線光通信網絡，網絡中通信節點分別為1、2、3…、9，圖中畫出了各節點之間的潛在鏈路，各通信節點的收發機數量統一限制為3，即各節點度約束為3。

若以節點間的距離作為權，則給定上述網絡圖G的權矩陣為W，矩陣各元素的大小設定如下：

若考慮無線光通信節點間通信的最大作用距離為18，則上述矩陣亦可表達為如下權矩陣：

對于上述實例，無線光通信網絡其度約束最小生成樹的最優解為{(1,3)(1,2)(6,8)(7,9)(1,4)(5,7)(2,8)(4,5)}和{(1,3)(2,3)(6,8)(7,9)(1,4)(5,7)(2,8)(4,5)}生成樹的最小權值為35；利用第3節給出的求取度約束最小生成樹的算法步驟，可以得到度約束最小生成樹的最優解為{(1,3)(1,2)(6,8)(7,9)(1,4)(5,7)(2,8)(4,5)}，其最小權值為35。

5 結語

通過對無線光通信網絡拓撲形成實例的計算表明，將無線光通信網絡的拓撲形成轉換為圖論的DCMST問題［12］，可以獲得網絡近似最優的樹形拓撲結構，為網絡鏈路的選擇和建立提供了參考。由于該算法并不保證每個通信節點達到其度的上限，導致獲得的網絡僅僅是連通，因此還需進一步研究利用其節點度的空余來增加冗余鏈路的問題，使其網絡更加健壯。此外，該算法還只適用于集中處理，因此還有必要進一步研究相關分布式算法。

參考文獻

［1］張斯珩.我國光纖通信技術的發展研究［J］.民營科技，2015（11）：85.

［2］Hirya Richard Edymond.Using a Directional Antenna to Achieve Quality Transmission on a Wireless Ad Hoc Net?work under Jamming Attacks［D］.長沙：湖南大學，2013.

［3］Zhuang J F，Casey M J. Multi-objective optimization techniques in topology control of free space optical net?works.IEEE Mi ICOM，Maryland University，MD.USA，2004：430-435.

［4］劉鋒，何東武，袁學海.模糊時間預測系統的Heuristic模型的改進［J］.遼寧師范大學學報（自然科學版），2002，25（2）：116-119.

［5］Desai A，Topology control and routing over wireless optical backbone networks［M］.Technical Report，Department of Electrical Engineering，University of Maryland，2003.

［6］ A.Desai and S.Milner，Autonomous reconguration in free-space optical sensor networks［J］.IEEE J.Sel.Areas Commun.2005（23）：1556-1563.

［7］L.Hu，Topology control for multihop packet radio networks［J］.IEEE Trans Commun，1993（41）：1474-1481.

［8］冷明.基于多水平方法的無向圖剖分及其在VLSI設計中的應用研究［D］.上海：上海大學，2008.

［9］顧立堯.帶有度約束的最小耗費生成樹的分支限界算法［J］.計算機應用與軟件 ，1989，6（6）：49-54.

［10］馬良，蔣馥.度約束最小生成樹的快速算法［J］.運籌與管理，1998，7（1）：1-5.

［11］宋海洲.求解度約束最小生成樹的快速近似算法［J］.系統工程學報，2006，21（3）：232-236.

［12］黃敏，李爾達，袁媛，鄭健.基于路網拓撲的聚類分析算法研究與實現［J］.中山大學學報（自然科學版），2015 ，54（6）：99-103.