程 樸 覃慧玲

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

1 引言

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

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

2 問題描述

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

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

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

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

3 算法的實現

就一般情形而言，度約束最小生成樹的問題是一個NP完備的難解問題，曾經出現過的一些精確算法（如分支定界法等［9］）都是指數時間的，無法求解中型以上規(guī)模的實際問題［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 計算機仿真

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

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

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

對于上述實例，無線光通信網絡其度約束最小生成樹的最優(yōu)解為{(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節(jié)給出的求取度約束最小生成樹的算法步驟，可以得到度約束最小生成樹的最優(yōu)解為{(1,3)(1,2)(6,8)(7,9)(1,4)(5,7)(2,8)(4,5)}，其最小權值為35。

5 結語

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

參考文獻

［1］張斯珩.我國光纖通信技術的發(fā)展研究［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］劉鋒，何東武，袁學海.模糊時間預測系統(tǒng)的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］.系統(tǒng)工程學報，2006，21（3）：232-236.

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