唐天兵，朱繼生，梁家榮

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

無線自組網(wǎng)可以靈活和快速地部署在許多應(yīng)用程序中，例如自動化戰(zhàn)場操作、搜索以及救災(zāi)。與有線網(wǎng)絡(luò)或蜂窩網(wǎng)絡(luò)不同，無線自組網(wǎng)中并沒有安裝物理主干基礎(chǔ)設(shè)施。通信會話可以通過單跳無線傳輸來實(shí)現(xiàn)，如果通信方足夠近，也可以通過中間節(jié)點(diǎn)進(jìn)行中繼。進(jìn)一步假設(shè)無線自組網(wǎng)中的所有節(jié)點(diǎn)V都分布在一個(gè)二維平面上，且最大傳輸距離為一個(gè)單元。無線自組網(wǎng)的拓?fù)浣Y(jié)構(gòu)可以建模為單元圓盤圖G=(V,E)，當(dāng)且僅當(dāng)兩個(gè)節(jié)點(diǎn)之間的距離最多為1時(shí)，兩個(gè)節(jié)點(diǎn)之間存在一條邊(見圖1)。

圖1 由單元圓盤圖組成的無線自組網(wǎng)

最近的研究指出，現(xiàn)有的ad hoc路由協(xié)議中拓?fù)涓禄蚵酚烧埱蟮姆汉闄C(jī)制大大降低了網(wǎng)絡(luò)容量。如果將控制包的廣播限制在網(wǎng)絡(luò)中主機(jī)的一個(gè)小子集內(nèi)，協(xié)議開銷就可以大大減少。文獻(xiàn)[1]研究表明：在無線傳感器網(wǎng)絡(luò)中引入虛擬骨干(virtual backbone)，可以有效地減少信息傳輸過程中的擁堵，極大地提高能量的使用率，延長網(wǎng)絡(luò)的壽命．這促進(jìn)了通過計(jì)算單元圓盤圖中的連通控制集(CDS)構(gòu)建虛擬主干的研究;文獻(xiàn)[2]中提出的移動能量補(bǔ)充策略VBMERS能有效地解決節(jié)點(diǎn)的能量饑餓問題，降低節(jié)點(diǎn)的失效率，進(jìn)而延長傳感器網(wǎng)絡(luò)的生存周期。

近年來，關(guān)于連通控制集的構(gòu)造算法己經(jīng)有很多的研究。因?yàn)樘摂M骨干網(wǎng)的規(guī)模會影響網(wǎng)絡(luò)性能，因此如何構(gòu)造最小連通控制集(MCDS)也就成為了研究的熱點(diǎn)。雖然構(gòu)造最小連通控制集早已被證明是NP難問題，但仍然有很多算法用于構(gòu)造MCDS，主要分為以下幾個(gè)種類。

第一類主要是用于構(gòu)造一般CDS，主要是基于文獻(xiàn)[3]中剪枝、文獻(xiàn)[4]中極大獨(dú)立集和文獻(xiàn)[5]中圖著色等一系列方法。

第二類主要是用于構(gòu)造多跳CDS上。比如文獻(xiàn)[6]中基于剪枝的r-hop CDS構(gòu)造方法和文獻(xiàn)[7]中d-Hop 2-連通容錯(cuò)支配集的分布式構(gòu)造算法。

第三類主要是關(guān)注于控制集的容錯(cuò)性和可靠性等方面，如文獻(xiàn)[8-9]和文獻(xiàn)[10-11]，其中大多與m-控制、k-連通性有關(guān)系。

而在無線自組網(wǎng)中，虛擬骨干網(wǎng)的質(zhì)量通常是由其近似因子來衡量的，近似因子是骨干網(wǎng)的大小與MCDS的大小之比;而虛擬骨干網(wǎng)的建設(shè)成本是通過消息復(fù)雜度和時(shí)間復(fù)雜度來度量的。表1總結(jié)了文獻(xiàn)[12-14]中提出的虛擬骨架的質(zhì)量和構(gòu)建成本。在節(jié)點(diǎn)可以連續(xù)移動的移動無線自組網(wǎng)中，虛擬骨干網(wǎng)不僅要時(shí)刻保持良好的質(zhì)量，而且在某一特定時(shí)刻，還要允許由于拓?fù)渥兓M(jìn)行有效的維護(hù)。遺憾的是，文獻(xiàn)中提出的虛擬骨干都不能有效地維護(hù)以保持良好的質(zhì)量。

表1 CDS構(gòu)造算法的性能比較

1 相關(guān)理論與定義

無線自組網(wǎng)是由無線接收機(jī)、發(fā)射機(jī)等移動終端組成的多跳、自組織的自治網(wǎng)絡(luò)。蜂窩移動通信網(wǎng)絡(luò)和無線局域網(wǎng)都需要預(yù)定義的基本網(wǎng)絡(luò)設(shè)施，如基站和接入服務(wù)站。然而，作為一個(gè)分散的分布式控制系統(tǒng)，在無線自組網(wǎng)中，每個(gè)用戶都具有路由器和主機(jī)的功能。因此，方便的終端可以實(shí)現(xiàn)簡單、快速的無線通信。無線自組網(wǎng)不依賴于任何現(xiàn)有或預(yù)定義的網(wǎng)絡(luò)基礎(chǔ)設(shè)施，終端節(jié)點(diǎn)隨機(jī)分配。因此，如何保證終端節(jié)點(diǎn)移動時(shí)的高質(zhì)量信號通信是研究領(lǐng)域的一個(gè)關(guān)鍵問題。無線傳感器網(wǎng)絡(luò)是分散的分布式系統(tǒng)。大量的傳感器以隨機(jī)的方式密集地布置在監(jiān)測區(qū)域內(nèi)。傳感器網(wǎng)絡(luò)用于從給定的位置或區(qū)域收集分布式信息。這些網(wǎng)絡(luò)由微型設(shè)備組成，每個(gè)設(shè)備都配有電源、微控制器、無線接口、少量內(nèi)存和一個(gè)或多個(gè)傳感器。傳感器用于收集物理參數(shù)，如光強(qiáng)度、聲音或溫度。由于無線通信范圍有限，傳感器節(jié)點(diǎn)通過中間節(jié)點(diǎn)進(jìn)行無線多跳路由通信。無線網(wǎng)絡(luò)包括無線自組網(wǎng)和無線傳感器網(wǎng)絡(luò)，近年來受到越來越多的關(guān)注，并在戰(zhàn)場、災(zāi)難恢復(fù)、會議、音樂會、環(huán)境檢測、健康應(yīng)用等方面得到了廣泛的應(yīng)用。

人們普遍認(rèn)為，無線網(wǎng)絡(luò)將是下一代網(wǎng)絡(luò)提供靈活部署和移動連接的理想和重要組成部分。為了研究無線網(wǎng)絡(luò)的算法和性質(zhì)，并對其正確性和性能給出數(shù)學(xué)證明，提出了許多模型，在此基礎(chǔ)上，給出了CDS相關(guān)的定義和術(shù)語。

單位圓盤圖(UDG):設(shè)V?R2為二維平面上的一組節(jié)點(diǎn)。這個(gè)歐幾里得圖G=(V,E)被稱為一個(gè)單位圓盤圖，如果圖中任何兩個(gè)節(jié)點(diǎn)相鄰當(dāng)且僅當(dāng)它們的歐幾里得距離最多是1。對于任意u,v∈V，它都有{u,v}∈E?d(u,v)<1。假設(shè)具有全向無線電天線的節(jié)點(diǎn)部署在一個(gè)平面的、暢通無阻的環(huán)境中。當(dāng)且僅當(dāng)兩個(gè)節(jié)點(diǎn)在相互傳輸范圍內(nèi)時(shí)，它們是相鄰的。圖1顯示了一個(gè)UDG示例，其中圓圈表示傳輸范圍?？梢钥吹剿泄?jié)點(diǎn)的傳輸范圍都是相同的。CDS構(gòu)造算法大多基于UDG的特點(diǎn)。然而，UDG模型是非常理想的。在現(xiàn)實(shí)中，無線電并不是全方位的，甚至像植物這樣的小障礙也能改變連通性。

獨(dú)立集(IS)和極大集(MIS):對于給定的G=(V,E)，一個(gè)子集I?V是G的一個(gè)獨(dú)立集，如果每一對u,v∈I，(u,v)?E。一個(gè)獨(dú)立集I被叫做極大獨(dú)立集則是如果不存在節(jié)點(diǎn)w∈VI，這樣的I∪{w}仍然也是G中的一個(gè)獨(dú)立集，則稱其為最大獨(dú)立集。

控制集(DS)和連通控制集(CDS):對于給定的G=(V,E)，一個(gè)子集D?V是G的一個(gè)控制集，如果每一個(gè)u∈VD，這里存在另外的點(diǎn)v∈D，都滿足(u,v)∈E。如文獻(xiàn)[15]所說找到一個(gè)最小控制集MDS是NP困難。一個(gè)控制集D，其誘導(dǎo)子圖G[D]是連通的，則稱其為連通控制集。

最小連通控制集(MCDS)：MCDS是具有最小基數(shù)的CDS。從文獻(xiàn)[16]中可知MCDS也是NP困難。

2 多跳極大獨(dú)立集模型

引理1：文獻(xiàn)[16]中設(shè)S為單位圓盤圖形G中的任意極大獨(dú)立集。對于?u∈S，證明S中距離u最多2跳的節(jié)點(diǎn)數(shù)最多為23；對于?u,v∈S，如果u,v相距兩跳，那么S中距離u或v最多3跳的節(jié)點(diǎn)數(shù)最多為64。

引理2：設(shè)S為單位圓盤圖形G中的任意極大獨(dú)立集。對于?u∈S，S中距離u最多3跳的節(jié)點(diǎn)數(shù)最多為44。

證明：注意到之前的模型都是用R為0.5的圓來模擬多跳無線網(wǎng)絡(luò)中的獨(dú)立節(jié)點(diǎn)，然而應(yīng)該注意到一個(gè)事實(shí)，即圓與圓之間并不是密鋪的，會存在一定的間隙。因此，用正六邊形來替代圓的話，會得到更為精確的結(jié)果，如圖2所示。

圖2 正六邊形替代單位圓盤

然而當(dāng)正六邊形在邊界上的時(shí)候有一個(gè)凸起會處于邊界外面(見圖3)，因此可以舍棄掉一個(gè)陰影部分的面積，為每一個(gè)R為0.5的圓分配5個(gè)陰影部分的面積來進(jìn)行計(jì)算。

圖3 陰影部分

3 近似因子分析

為了達(dá)到最低消息復(fù)雜度的目標(biāo)，其構(gòu)造方法如圖4所示，主要包含三個(gè)步驟：步驟1構(gòu)造一個(gè)森林，其中每棵樹的根在其一跳鄰居中ID最小的節(jié)點(diǎn)上；步驟2收集鄰接信息；步驟3用于連接鄰接樹。最初所有節(jié)點(diǎn)都是白色的。操作和廣播消息如文獻(xiàn)[16]所述。

圖4 構(gòu)造方法

定理：所生成的連通控制集的大小最多為143·opt+33。

從文獻(xiàn)[16]中可知：

|S1|+|S2|≤4·opt+1

且

|S3|≤|S2|

2-|S3|

D=|S1|+|S2|+|S3|+|S4|≤

44≤143·opt+33

4 結(jié)束語

該文在保證構(gòu)建消息最優(yōu)的連通控制集的情況下，建立了一種新的求解極大獨(dú)立集的模型，注意到在之前的文章中都是通過圓來建立求解三條內(nèi)的極大獨(dú)立集，但是顯然在圓與圓之間是有縫隙的，這會造成一定的誤差。而通過使用正六邊形來代替R為0.5的圓，顯然可以求得一個(gè)更為精確的三跳內(nèi)極大獨(dú)立集，從而提高了結(jié)果的準(zhǔn)確度，得到了一個(gè)更小的其值為143opt+33連通控集近似比。在文獻(xiàn)[17]中證明了單位磁盤圖中的MCDS有一個(gè)PTAS，這意味著它可以被近似到任何程度。然而，具有O(nlogn)消息復(fù)雜度的最佳算法的性能比為8，線性消息復(fù)雜度的最佳算法得到的連通控制集最多為143opt+33，因此，未來的研究之一是設(shè)計(jì)更好的啟發(fā)式算法來彌補(bǔ)這一差距。