程 樸 覃慧玲

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

1 引言

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

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

2 問題描述

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

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

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

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

3 算法的實現(xiàn)

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

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

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

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

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

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

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

計算圖的總權(quán)重，輸出圖及總權(quán)重。

圖1 無線光通信網(wǎng)絡(luò)示意圖

4 計算機仿真

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

若以節(jié)點間的距離作為權(quán)，則給定上述網(wǎng)絡(luò)圖G的權(quán)矩陣為W，矩陣各元素的大小設(shè)定如下：

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

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

5 結(jié)語

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

參考文獻

［1］張斯珩.我國光纖通信技術(shù)的發(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］.長沙：湖南大學(xué)，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］劉鋒，何東武，袁學(xué)海.模糊時間預(yù)測系統(tǒng)的Heuristic模型的改進［J］.遼寧師范大學(xué)學(xué)報（自然科學(xué)版），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設(shè)計中的應(yīng)用研究［D］.上海：上海大學(xué)，2008.

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

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

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

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