無線自組網(wǎng)絡(luò)中的消息最優(yōu)的連通控制集

唐天兵，朱繼生，梁家榮

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

0 引 言

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

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

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

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

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

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

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

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

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

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

無線自組網(wǎng)是由無線接收機、發(fā)射機等移動終端組成的多跳、自組織的自治網(wǎng)絡(luò)。蜂窩移動通信網(wǎng)絡(luò)和無線局域網(wǎng)都需要預(yù)定義的基本網(wǎng)絡(luò)設(shè)施，如基站和接入服務(wù)站。然而，作為一個分散的分布式控制系統(tǒng)，在無線自組網(wǎng)中，每個用戶都具有路由器和主機的功能。因此，方便的終端可以實現(xiàn)簡單、快速的無線通信。無線自組網(wǎng)不依賴于任何現(xiàn)有或預(yù)定義的網(wǎng)絡(luò)基礎(chǔ)設(shè)施，終端節(jié)點隨機分配。因此，如何保證終端節(jié)點移動時的高質(zhì)量信號通信是研究領(lǐng)域的一個關(guān)鍵問題。無線傳感器網(wǎng)絡(luò)是分散的分布式系統(tǒng)。大量的傳感器以隨機的方式密集地布置在監(jiān)測區(qū)域內(nèi)。傳感器網(wǎng)絡(luò)用于從給定的位置或區(qū)域收集分布式信息。這些網(wǎng)絡(luò)由微型設(shè)備組成，每個設(shè)備都配有電源、微控制器、無線接口、少量內(nèi)存和一個或多個傳感器。傳感器用于收集物理參數(shù)，如光強度、聲音或溫度。由于無線通信范圍有限，傳感器節(jié)點通過中間節(jié)點進行無線多跳路由通信。無線網(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é)點。這個歐幾里得圖G=(V,E)被稱為一個單位圓盤圖，如果圖中任何兩個節(jié)點相鄰當(dāng)且僅當(dāng)它們的歐幾里得距離最多是1。對于任意u,v∈V，它都有{u,v}∈E?d(u,v)<1。假設(shè)具有全向無線電天線的節(jié)點部署在一個平面的、暢通無阻的環(huán)境中。當(dāng)且僅當(dāng)兩個節(jié)點在相互傳輸范圍內(nèi)時，它們是相鄰的。圖1顯示了一個UDG示例，其中圓圈表示傳輸范圍?？梢钥吹剿泄?jié)點的傳輸范圍都是相同的。CDS構(gòu)造算法大多基于UDG的特點。然而，UDG模型是非常理想的。在現(xiàn)實中，無線電并不是全方位的，甚至像植物這樣的小障礙也能改變連通性。

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

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

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

2 多跳極大獨立集模型

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

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

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

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

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

圖3 陰影部分

3 近似因子分析

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

圖4 構(gòu)造方法

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

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