程 樸 覃慧玲

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

1 引言

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

無(wú)線光通信網(wǎng)絡(luò)初始化過(guò)程中，一個(gè)通信節(jié)點(diǎn)面臨著多個(gè)候選通信對(duì)象，而節(jié)點(diǎn)內(nèi)通信收發(fā)機(jī)的數(shù)量又是有限的（即節(jié)點(diǎn)的度），因此，需要獲得一種拓?fù)湫纬桑ㄍ負(fù)淇刂疲┧惴▉?lái)實(shí)現(xiàn)通信鏈路的優(yōu)化選擇，以期形成連通的最優(yōu)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。目前，國(guó)內(nèi)外已有一些針對(duì)無(wú)線光通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面的研究［3］。拓?fù)淇刂浦饕抢肏euristic方法［4］計(jì)算一種最優(yōu)的拓?fù)?，使得物理層的誤碼率與網(wǎng)絡(luò)層的擁塞率都達(dá)到最?。晃墨I(xiàn)［5］中，主要是針對(duì)無(wú)線光通信網(wǎng)絡(luò)中環(huán)形拓?fù)涞目刂七M(jìn)行研究。文獻(xiàn)［6］研究FSO的重點(diǎn)是通過(guò)控制網(wǎng)絡(luò)擁塞最小的拓?fù)浣Y(jié)構(gòu)來(lái)實(shí)現(xiàn)動(dòng)態(tài)重構(gòu)。文獻(xiàn)［7］中提出了一種新的分組無(wú)線網(wǎng)絡(luò)拓?fù)淇刂疲∟TC）的算法，以實(shí)現(xiàn)高吞吐量的連接。本文主要以無(wú)線光通信網(wǎng)絡(luò)樹形結(jié)構(gòu)為對(duì)象，將網(wǎng)絡(luò)的拓?fù)湫纬蓡栴}轉(zhuǎn)換為度約束最小生成樹（DCMST）問題，并引入了一種快速近似算法來(lái)加以求解。

2 問題描述

無(wú)線光通信網(wǎng)絡(luò)的拓?fù)湫纬傻哪康氖莾?yōu)化選擇網(wǎng)絡(luò)中各節(jié)點(diǎn)的通信對(duì)象，建立節(jié)點(diǎn)間的通信傳輸路徑，實(shí)現(xiàn)網(wǎng)絡(luò)各節(jié)點(diǎn)的互連互通。結(jié)合圖論理論，可以將無(wú)線光通信網(wǎng)絡(luò)用圖論的方式加以表達(dá)。由于無(wú)線光通信網(wǎng)絡(luò)點(diǎn)對(duì)點(diǎn)間的通信鏈路往往是雙向的傳輸?shù)模虼藷o(wú)線光通信網(wǎng)絡(luò)的連通圖可以當(dāng)作無(wú)向圖［8］

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

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

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

3 算法的實(shí)現(xiàn)

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

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

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

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

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

4）檢查BW的第1列對(duì)應(yīng)的邊是否可以用：如果該邊所關(guān)聯(lián)的頂點(diǎn)的度檢查值都大于0，而且將該邊加入到圖T后，圖不會(huì)形成圈，則BW的第1列對(duì)應(yīng)的邊可以用，否則該邊不可以用，從BW中刪除該邊，更新BW，直到BW的第1列對(duì)應(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)的頂點(diǎn)加入到圖中，并將該邊所關(guān)聯(lián)的頂點(diǎn)（不妨設(shè)該邊所關(guān)聯(lián)的頂點(diǎn)為ik和jk），所對(duì)應(yīng)的度檢查值減去1（即：，并從BW中刪除該邊更新BW，轉(zhuǎn)步驟4）。

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

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

4 計(jì)算機(jī)仿真

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

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

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

對(duì)于上述實(shí)例，無(wú)線光通信網(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é)語(yǔ)

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

參考文獻(xiàn)

［1］張斯珩.我國(guó)光纖通信技術(shù)的發(fā)展研究［J］.民營(yíng)科技，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］.長(zhǎng)沙：湖南大學(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é)海.模糊時(shí)間預(yù)測(cè)系統(tǒng)的Heuristic模型的改進(jìn)［J］.遼寧師范大學(xué)學(xué)報(bào)（自然科學(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］冷明.基于多水平方法的無(wú)向圖剖分及其在VLSI設(shè)計(jì)中的應(yīng)用研究［D］.上海：上海大學(xué)，2008.

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

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

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

［12］黃敏，李爾達(dá)，袁媛，鄭健.基于路網(wǎng)拓?fù)涞木垲惙治鏊惴ㄑ芯颗c實(shí)現(xiàn)［J］.中山大學(xué)學(xué)報(bào)（自然科學(xué)版），2015 ，54（6）：99-103.