張　昭

(浙江師范大學　浙江金華　321004)

(hxhzz@sina.com)

?

無線傳感器網(wǎng)絡(luò)虛擬骨干近似算法綜述

張昭

(浙江師范大學浙江金華321004)

(hxhzz@sina.com)

Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network

Zhang Zhao

(ZhejiangNormalUniversity,Jinhua,Zhejiang321004)

AbstractUsing virtual backbone in wireless sensor network can effectively save energy, reduce interference, and prolong lifetime, which has a wide application in the field of geometric routing and topology control. Virtual backbone can be modeled as a connected dominating set (CDS) in a graph. This paper introduces the state of art of approximation algorithms on CDS and its variations. The focus is put on theoretical results and methods. The purpose is to provide a reference for researchers who are interested in this field.

Key wordswireless sensor network (WSN); virtual backbone; connected dominating set (CDS); approximation algorithm; performance ratio

摘要在無線傳感器網(wǎng)絡(luò)中應(yīng)用虛擬骨干，可以有效地節(jié)約能量、減少干擾、延長網(wǎng)絡(luò)壽命，在幾何路由算法和網(wǎng)絡(luò)拓撲控制等方面具有廣泛的應(yīng)用.虛擬骨干可以模型化為圖中的連通控制集.主要從近似算法角度介紹連通控制集及其各種變形在國內(nèi)外的研究現(xiàn)狀及最新進展，側(cè)重于研究方法和理論結(jié)果，為相關(guān)研究人員提供參考.

關(guān)鍵詞無線傳感器網(wǎng)絡(luò)；虛擬骨干；連通控制集；近似算法；近似比

無線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)是一種分布式的傳感網(wǎng)絡(luò)，它由大量可以感知外部世界的傳感器組成，并通過無線通信方式形成一個多跳的自組織網(wǎng)絡(luò).無線傳感器網(wǎng)絡(luò)在軍事和民用等領(lǐng)域具有廣泛的應(yīng)用，如戰(zhàn)場監(jiān)控、環(huán)境監(jiān)測、交通監(jiān)管、智能家居、醫(yī)療衛(wèi)生等[1].由于無線傳感器網(wǎng)絡(luò)沒有固定的基礎(chǔ)設(shè)施，傳感器主要以自組織和多跳的方式協(xié)作地完成信息的傳輸和共享，故如何有效地進行拓撲控制和路由選擇以獲得一個高效、可靠、節(jié)能的自組織網(wǎng)絡(luò)是一個具有挑戰(zhàn)性的課題.如果信息傳輸過程使用簡單的洪泛(flooding)方式(即每個傳感器將它所感知的信息立即播報出去)，則極易造成能量的耗費并產(chǎn)生大量的信號干擾，引起廣播風暴(broadcast storm)[2].文獻[3]研究表明：在無線傳感器網(wǎng)絡(luò)中引入虛擬骨干(virtual backbone)，可以有效地減少信息傳輸過程中的擁堵、極大地提高能量的使用率、延長網(wǎng)絡(luò)的壽命.

虛擬骨干可以模型化為圖論中的連通控制集(connected dominating set, CDS).給定圖G=(V,E)，頂點V的子集C稱為控制集，如果VC中的每個頂點都在C中有鄰點.進一步，如果由C導出的子圖G[C]是連通的，則稱C為連通控制集.計算最小連通控制集是經(jīng)典的NP-難問題[4].因此，人們更感興趣的是如何對它設(shè)計有近似比(performance ratio)保證的多項式時間近似算法.事實上，Guha和Khuller在文獻[5]中構(gòu)造了一個從最小集合覆蓋問題(minimum set cover)到最小連通控制集問題的保近似的約化(approximation preserving reduction)，因此，最小連通控制集問題是SC-難的.這意味著：除非NP?DTIME(nO(loglog n))，否則對任意0<ρ<1，最小連通控制集問題不存在近似比可以達到ρlnn的多項式時間近似算法.然而，利用無線傳感器網(wǎng)絡(luò)的特殊性質(zhì)，有可能得到該問題的更好近似.另外，人們希望虛擬骨干具有各種良好的性質(zhì)，因此，連通控制集的各種變形也成為國際相關(guān)研究的熱點之一.

研究連通控制集及其各種變形的近似算法，不僅是研究虛擬骨干自身的需要，還是其它相關(guān)研究的基礎(chǔ).

例如在幾何路由(geometric routing)的局域算法(local algorithm)中，Kuhn等人[6]給出了一個GOAFR+算法，并證明了對于具有有界度(bounded degree)的單位圓盤圖(unit disk graph, UDG)，該算法可以得到一個長度不超過O(c2)的路徑，其中c為最優(yōu)路徑長度.文獻[7]指出，O(c2)是局域路由算法所能企及的最好可能.但對于度數(shù)無常數(shù)界的單位圓盤圖來說，該算法質(zhì)量無法保證.為了解決這個問題，Wang等人在文獻[8]中設(shè)計了一個推廣GOAFR+算法.該算法先構(gòu)造了一個具有有界度的連通控制集作為路由骨干網(wǎng)，再在這個路由骨干網(wǎng)上應(yīng)用GOAFR+算法就可以得到上述漸近最優(yōu)的路徑長度.

又如無線傳感器網(wǎng)絡(luò)覆蓋的最大生命期問題(maximum lifetime of coverage)中，人們希望通過對傳感器工作睡眠狀態(tài)的控制來實現(xiàn)網(wǎng)絡(luò)生命期的最大化.Berman等人[9]發(fā)現(xiàn)，該問題可以轉(zhuǎn)化為一系列最小權(quán)連通控制集問題來求解，如果最小權(quán)連通控制集問題有多項式時間ρ-近似算法，則最大生命期問題就存在多項式時間(ρ+ε)-近似算法，其中ε是任意一個大于0的實數(shù).

事實上，一個好的連通控制集可以反映出網(wǎng)絡(luò)的主要特征，借助它去實現(xiàn)整個網(wǎng)絡(luò)的功能可以取得更好的產(chǎn)出比.因此，如何構(gòu)建一個好的連通控制集是一個很有意義的課題.

本文旨在綜述最小連通控制集問題及其主要變形的發(fā)展現(xiàn)狀，側(cè)重于確定性算法的主要研究方法和理論結(jié)果，并對主要研究方法做一個小結(jié)，對相關(guān)研究方向的發(fā)展做一個展望.

1虛擬骨干近似算法研究現(xiàn)狀

近年來，由于無線傳感器網(wǎng)絡(luò)的興起，連通控制集問題及其各種變形引起國際同行的廣泛研究.Du和Wan在文獻[10]中對各種與連通控制集相關(guān)的算法問題給出了詳細的方法性論述.本文對連通控制集近似算法方面的研究現(xiàn)狀和研究方法作概要性的介紹，以期為相關(guān)研究人員提供一個總體性的參考.

1.1一般圖上連通控制集的近似算法

Ruan等人在文獻[11]中又給出了最小連通控制集的一個(2+lnΔ)-近似算法.雖然該近似比只比前者改進了一點點，但在研究方法上卻有一個新的突破.事實上，很多問題的貪婪算法都可以用勢函數(shù)(potential function)來描述：設(shè)A,B是2個集合，勢函數(shù)f(A)表示集合A的收益，差分ΔBf(A)=f(A∪B)-f(A)表示在A的基礎(chǔ)上增加B中元素后新增的收益(或稱邊際效益(marginal profit))；貪婪策略從A=?開始，迭代地選擇元素x加入A，使得Δxf(A)最大；直至對任意x都有Δxf(A)=0時(稱為終止準則)，算法終止.稱勢函數(shù)f為單調(diào)增函數(shù)，如果對任意的A?B，都有f(A)≤f(B).稱勢函數(shù)f為次模函數(shù)，如果對任意的A?B和任意的集合C，都有:

ΔCf(A)≥ΔCf(B),

(1)

即f滿足邊際效益遞減律.經(jīng)典理論表明，如果勢函數(shù)是單調(diào)增的次模函數(shù)且f(?)=0，則貪婪算法的近似比不超過H(γ)，其中γ=max{f(x)}[12].遺憾的是，對于最小連通控制集問題，同時滿足終止準則和次模性要求的勢函數(shù)一直未能找到.Ruan等人的貢獻在于，他們發(fā)現(xiàn)算法分析中只需要式(1)對一些與最優(yōu)解和貪婪解相關(guān)的特定集合成立即可(并不需要對任何集合A,B,C都成立)，甚至當式(1)右端減去一個常數(shù)c時都可以得到對數(shù)級近似.具體來說，他們構(gòu)造了一種非次模勢函數(shù)f.假設(shè)Ag={x1,x2,…,xg}為貪婪算法的輸出解，其中元素x1,x2,…,xg按貪婪算法選擇它們的順序排列.對i=1,2,…,g，記Ai={x1,x2,…,xi}.又設(shè)B={y1,y2,…,ym}為最優(yōu)解.對j=1,2,…,m，記Bj={y1,y2,…,yj}.由于B導出的子圖連通，故可以選擇y1,y2,…,ym的排序，使得對任意的j，Bj導出的子圖都連通.Ruan等人證明了：對任意的i和j都有:

Δyjf(Ai-1)≥Δyjf(Ai-1∪Bj-1)-1.

(2)

應(yīng)用式(2)他們得到了最小連通控制集的(2+lnΔ)-近似.該方法突破了傳統(tǒng)貪婪算法次模性的要求，被廣泛應(yīng)用于后續(xù)工作中，包括社會網(wǎng)絡(luò)中最小種子(seed)集合的選擇問題等[13].Du等人在文獻[14]中又進一步研究了該方法的變形，給出了最小連通控制集的一個(1+ε)ln(Δ-1)-近似算法，其中ε是任意正實數(shù).

1.2單位圓盤圖上連通控制集的近似算法

單位圓盤圖(UDG)是均質(zhì)無線傳感器網(wǎng)絡(luò)(homogeneous WSN)中普遍采用的一種數(shù)學模型：圖中每個點對應(yīng)于平面上的一個傳感器，2個點在圖中相鄰的充要條件是相應(yīng)傳感器之間的歐氏距離不超過1(單位長度).Clark等人[15]證明：即使局限到單位圓盤圖中，最小連通控制集問題仍然是NP-困難的.然而，利用單位圓盤圖的幾何性質(zhì)，該問題可以得到較好的近似比.

Cheng等人在文獻[16]中給出了單位圓盤圖中最小連通控制集的第1個多項式時間近似方案(polynomial time approximation scheme, PTAS)，即在(與ε相關(guān)的)多項式時間內(nèi)逼近最優(yōu)解的精度可以達到1+ε.該算法以劃分平移方法(technique of partition and shifting)為框架.劃分是“分而治之”思想的體現(xiàn)：把眾多小區(qū)域上的解組裝起來得到大區(qū)域上的解.組裝過程中會產(chǎn)生一定的損失，損失主要發(fā)生在小區(qū)域的邊界地帶.當小區(qū)域尺寸足夠大時，在概率意義下邊界會相對很“薄”，從而損失會是一個ε小量.平移技巧正是這種概率思想確定性的實現(xiàn).劃分平移方法是近似算法中的一個經(jīng)典的手段[17-18].對于最小連通控制集來說，應(yīng)用該方法的難點在于連通性的處理.Cheng等人首次提出了內(nèi)部區(qū)域和邊界區(qū)域的概念，其算法在得到各內(nèi)部區(qū)域在一定意義下的最優(yōu)解后，迭加一個常數(shù)近似算法落在邊界區(qū)域中的點集，通過內(nèi)部區(qū)域與邊界區(qū)域一定程度的重合，保證了算法輸出解的連通性要求.但該算法的分析無法推廣到高維空間中，因為其分析中用到了平面上的2條直線不平行則相交這一性質(zhì).Zhang等人在文獻[19]中引入了新的分析技巧，將該PTAS近似算法推廣至任意維空間的單位球圖(unit ball graphs, UBG)上，其關(guān)鍵是一種“微小補償”的思想.具體來說，為了得到最優(yōu)解與算法輸出解之間的一個比較，需要考慮最優(yōu)解在每個小區(qū)域上的限制，并將它改造成為小區(qū)域上具有給定意義的可行解.該算法分析在改造過程中加入了一些新的點，并證明了所加的點數(shù)可以被最優(yōu)解落在邊界區(qū)域中的點數(shù)所控制，結(jié)合平移技巧，后者是一個ε小量(微小補償).

PTAS的近似比較小，但計算時間太長.為此，有必要探索時間復雜度較低的分布式算法.該方面最初的研究是由Wan等人[20]給出的，他們先通過對一棵廣度優(yōu)先搜索樹的頂點進行著色，得到一個具有如下性質(zhì)的極大獨立集(maximal independent set)：如果將該極大獨立集任意劃分成2部分，這2部分之間距離最近的2個點都是2-步可達的.基于這一性質(zhì)，最多加一個點就可以融合至少2個分支，從而連通它們所加的點數(shù)不超過獨立點數(shù).因此，要得到近似比分析，就要估計最大獨立數(shù)α與最小連通控制集的點數(shù)γc之間的關(guān)系.Wan等人證明了：在單位圓盤圖中，α≤4γc+1，從而他們的算法近似比不超過8.這方面的研究與幾何中的packing問題密切相關(guān)，即給定區(qū)域中最多可以裝入多少個獨立點.經(jīng)過一系列的改進[21-26]，應(yīng)用了大量幾何工具，包括Voronoi digram、歐拉公式等，目前該關(guān)系方面最好的界[26]為α≤3.3371γc+3.6741.另一個改進近似比的方向是減少連接部分所加的點數(shù).Li等人[27]運用最小點數(shù)Steiner樹的思想構(gòu)造了一個近似算法，貪婪地用最大度點去融合連通分支，通過利用單位圓盤圖中每個點最多與5個分支相鄰這一事實，他們證明了該算法連接部分所用的點數(shù)不超過最優(yōu)解點數(shù)的(2+ln 4)≈2.4倍.Kim等人在文獻[28]中運用類似的思想給出了3維單位球圖中最小連通控制集的一個分步式近似算法，其近似比為14.937，但在分析中有一個錯誤.Gao等人在文獻[29]中提出了一種新的投影方法糾正了這一錯誤.這方面研究的難點在于高維空間中packing問題的幾何分析.

1.3容錯連通控制集的近似算法

在實際應(yīng)用中，無線傳感器網(wǎng)絡(luò)往往具有很強的動態(tài)性，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)經(jīng)常會由于能量耗盡或元件故障而發(fā)生改變.因此，人們希望虛擬骨干具有一定的容錯性(fault-tolerance)，即在部分傳感器出現(xiàn)故障的情況下整個網(wǎng)絡(luò)仍能正常通信的能力.該問題可模型化為最小k-連通m-重控制集問題(簡稱(k,m)-CDS問題)，即要求虛擬骨干C以外的任一點都至少被C中m個點所控制，而C導出的子圖的連通度至少為k.采用(k,m)-CDS作為虛擬骨干，即使min{k-1,m-1}個節(jié)點發(fā)生故障，虛擬骨干仍能正常工作.

Dai和Wu在2005年最先將最小(k,m)-CDS問題引入容錯虛擬骨干的研究中[30]，并給出了最小(k,k)-CDS的3個啟發(fā)式算法，但沒有給出近似比分析.表1總結(jié)了該研究領(lǐng)域中有近似比保證的主要研究結(jié)果.由于只總結(jié)與容錯性相關(guān)的結(jié)果，故表1的k和m中至少有一個大于1.

Table 1　Current Results for Fault-Tolerant CDS

對于單位圓盤圖，Wang等人在文獻[36]中給出了(2,1)-CDS的一個72-近似算法.該算法提出了一種把連通控制集的連通度提升到2的方法：利用1-連通但非2-連通圖的塊分解(block decompostion)結(jié)構(gòu)(塊是極大的無割點的子圖)，不斷地用聯(lián)結(jié)不同塊的最短路去融合塊，直到得到一個2-連通圖.該算法近似比分析中的關(guān)鍵是：在連通度達到2之前，總存在一條可以融合塊的路，其長度不超過9，從而把連通度由1提升到2的過程中所加的點數(shù)不超過(1,1)-CDS的8倍.

Shang等人在文獻[37]中提出了一種在單位圓盤圖中尋找m-重控制集的方法：迭代地選取m個極大獨立集，它們的并即構(gòu)成一個m-重控制集.利用單位圓盤圖中的獨立點比較稀疏這一性質(zhì)，Shang等人給出了單位圓盤圖中(1,m)-CDS的常數(shù)近似算法，并進一步運用Wang等人提升連通度的方法[36]，得到了m≥2時單位圓盤圖中(2,m)-CDS的常數(shù)近似算法.注意到m≥2時，每步迭代中最多增加2個點就可以減少塊的個數(shù).在這種條件下，把連通度由1提升到2的過程中所加的點數(shù)不超過(1,1)-CDS的2倍.

Kim等人在文獻[38]中得到了單位圓盤圖中最小(3,m)-CDS問題的常數(shù)近似算法，但該算法非常復雜，近似比也很大，如(3,3)-CDS的近似比為280.Wang等人于2015年在文獻[39]中運用2-連通但非3-連通圖的Tutte-分解簡化了該算法，并改進了近似比.特別地，(3,3)-CDS的近似比可以降到62.3.

對于一般圖，Zhou等人在文獻[33]中設(shè)計了一個非次模的勢函數(shù)，給出了(1,m)-CDS的一個貪婪算法，其近似比不超過2+H(Δ+m-2).考慮到最小(k,m)-CDS問題的不可ρlnn-近似性，該近似比達到了漸近最優(yōu).以此為基礎(chǔ)，Shi等人在文獻[34]中利用塊分解結(jié)構(gòu)將連通度由1提升到了2.與文獻[36-37]不同的是，文獻[34]以塊的個數(shù)為勢函數(shù)，用貪婪策略選擇所加的路，注意到塊的個數(shù)并不是次模函數(shù).但是，文獻[34]找到了最優(yōu)解的一種分解結(jié)構(gòu)，導出了其元素的一種排列方式，證明了與式(2)具有相似味道的一個不等式，從而在m≥2的條件下得到了一般圖中(2,m)-CDS的漸近最優(yōu)的近似算法.將它應(yīng)用到單位圓盤圖中，可以改進Shang等人[37]中的近似比.

基于Tutte分解，我們用非次模勢函數(shù)的方法，在m≥3的條件下得到了一般圖中最小(3,m)-CDS的一個漸近最優(yōu)的近似算法.特別地，將它應(yīng)用到單位圓盤圖上，?m≥3，近似比都不超過27.

1.4最小權(quán)連通控制集的近似算法

在一般圖中，Guha和Khuller在文獻[40]中給出了一個近似比不超過(1.35+ε)lnn的近似算法.該結(jié)果是最小點加權(quán)Steiner樹問題的一個應(yīng)用.Klein和Ravi在文獻[41]中首先提出了一種蜘蛛分解的方法(spider decomposition)，得到了最小點加權(quán)Steiner樹問題的2ln |R|-近似，其中R為Steiner樹問題的終端集合(terminal set).Guha和Khuller在文獻[40]中將上述方法推廣到分支蜘蛛分解(branch spider decomposition)，進而把近似比改進為(1.35+ε)ln |R|.特別地，取R=V，可以得到最小權(quán)連通控制集的(1.35+ε)lnn-近似.該結(jié)果于1999年得到，至今一直沒有得到改進.

單位圓盤圖中最小權(quán)連通控制集的第1個常數(shù)近似算法由Ambühl等人在文獻[42]中給出.他們首先提出了一個特殊的覆蓋問題：從一些圓心在某水平帶子之外的圓盤中選擇一部分去覆蓋分布在水平帶子中的點，目標是所選圓盤的總權(quán)重最小.Ambühl等人設(shè)計了一種動態(tài)規(guī)劃算法，在多項式時間內(nèi)可以得到該問題的最優(yōu)解;然后，他們將單位圓盤圖中的最小權(quán)控制集問題分解為一系列水平帶子覆蓋問題和垂直帶子覆蓋問題，得到最小權(quán)控制集問題的一個72-近似;最后，再將所得控制集連通起來，其連通部分的近似比為17.

Huang等人在文獻[43]中引入了雙重劃分(double-partition)的技巧，將上述控制部分和連通部分的近似比分別降低到了6+ε和4.該算法在求解控制集階段的思想是：將盡可能多的帶子覆蓋問題綜合起來求解，以減少最優(yōu)解中每個圓盤所使用的重復度.算法的關(guān)鍵是如何分解原問題，使得分解出來的子問題與原問題相容，即原問題的最優(yōu)解能夠成為子問題的可行解，同時還必須保證分解得到的子問題數(shù)目不超過原問題規(guī)模的多項式.為此，文獻[43]提出了一個“沙漏”(sand glass)的幾何概念，應(yīng)用它簡化了分解問題的復雜度，使得算法可以在多項式時間內(nèi)完成.該算法在連通階段的思想是：把問題轉(zhuǎn)化為邊加權(quán)最小支撐樹問題，運用單位圓盤中每個點最多有5個相鄰分支這一事實，證明了最優(yōu)解中每個點被重復利用的次數(shù)不超過4，從而得到連通部分的4-近似.

上述思想被進一步深化.Dai和Yu在文獻[44]中將求解單位圓盤圖中最小權(quán)控制集的近似比改進到5+ε，該近似比又被Zou等人[45]和Erlebach與Mihalák[46]改進到4+ε.這些改進均基于對動態(tài)規(guī)劃算法的改進，即不再是一條帶子一條帶子地分別求解，而是將具有相同奇偶性標號的帶子綜合起來求解，從而進一步節(jié)省了最優(yōu)解中每個圓盤被使用的重復度.

推廣上述思想，Erlebach等人在文獻[47]中得到了單位圓盤圖中最小權(quán)2-重控制集問題的一個(6+ε)-近似算法.Zhang等人在文獻[48]中對任意正整數(shù)m，得到了單位圓盤圖中最小權(quán)m-重控制集問題的(4+ε)-近似.為此，文獻[48]首先提出了一個最小權(quán)奇偶帶子多重覆蓋問題(minimum weight parity strip multi-cover)，證明了該問題可以用動態(tài)規(guī)劃在多項式時間內(nèi)求解;然后將原問題分解為4個最小權(quán)奇偶帶子多重覆蓋問題，從而得到該問題的(4+ε)-近似.文獻[48]引入了鉆石(diamond)和楔(wedge)等幾何概念，解決了問題分解的相容性和多項式時間可實現(xiàn)性等難點.

應(yīng)用Steiner樹的思想，最小權(quán)連通控制集連通部分的近似比可以降低到Δρ2，其中ρ為最小邊權(quán)Steiner樹問題的近似比，Δ為圖的最大度.事實上，對每條邊uv賦以權(quán)值(w(u)+w(v))2，就可以把點賦權(quán)的問題轉(zhuǎn)化為邊賦權(quán)的問題，而每個點的權(quán)在最小邊權(quán)Steiner樹的求解中被重復利用的次數(shù)不超過Δ2.Zou等人[49]注意到：任何一個連通的單位圓盤圖中都存在一個連通的支撐子圖，其最大度不超過5.結(jié)合目前已知最好的ρ值1.39[50]，單位圓盤圖中最小權(quán)控制集問題連通部分的近似比不超過3.475.

Zhang等人在文獻[51]中研究了最小權(quán)k-連通m-重控制集問題，通過證明任意2-連通的單位圓盤圖中都存在一個2-連通支撐子圖，其最大度不超過5，并利用最小權(quán){0,1,2}-Steiner樹問題的2-近似算法[52]，最小權(quán)2-連通m-重控制集問題在單位圓盤圖中存在(3+ε)-近似.

1.5考慮拉伸因子的連通控制集的近似算法

通過虛擬骨干進行信息傳輸，可能造成時間上的極大延遲.考慮到信息交流的時效問題，Ding等人[53]提出了最小路由費用虛擬骨干(minimum routing cost virtual backbone)的概念，簡稱MOC-CDS.用distG(u,v)表示圖G中u,v兩點的最短路長度，用distC(u,v)表示連接u,v兩點的中間節(jié)點全在C中的最短路長度.連通控制集C稱為MOC-CDS，如果

?u,v,distC(u,v)=distG(u,v).

(3)

Ding等人證明了MOC-CDS是SC-難問題，并給出了一個H(Δ(Δ-1)2)-近似算法.該算法的關(guān)鍵一步是證明了式(3)等價于：對任意距離恰為2的u,v點都有

distC(u,v)=distG(u,v)，

從而可以把MOC-CDS的求解轉(zhuǎn)化為一個最小集合覆蓋問題，再應(yīng)用最小集合覆蓋問題的貪婪算法即得上述近似比.

數(shù)值實驗顯示MOC-CDS的尺寸非常大[53].為了平衡虛擬骨干的尺寸和路由費用，Ding等人[54]又提出了αMOC-CDS的概念：對于給定的常數(shù)α≥1，任意u,v點都滿足：

distC(u,v)≤α×distG(u,v)，

這里的α對應(yīng)于計算幾何中的拉伸因子(stretch factor).對于α≥5，Du等人給出了單位圓盤圖中αMOC-CDS的常數(shù)近似算法[55-56]，并進一步運用劃分平移的思想給出了PTAS[57].

一個自然的問題是α<5時會如何?Liu等人在文獻[58-59]中部分地回答了該問題.定義gMOC-CDS為一個滿足如下條件的連通控制集C：對給定的常數(shù)k，任意u,v點都滿足:

distC(u,v)≤g(u,v)=

(4)

文獻[58]證明了C為gMOC-CDS的充要條件是：任意distG(u,v)≤k+1的點對u,v都滿足distC(u,v)≤distG(u,v)+4.算法先找出一個極大獨立集，然后在任意滿足distG(u,v)≤k+1的獨立點對u,v之間都添加一條最短路，可以證明該算法具有常數(shù)近似比.進一步，運用劃分平移的方法，可以得到gMOC-CDS的PTAS.注意到k=1時式(4)中的乘法因子1+4k=5，當k增大時該乘法因子單調(diào)遞減趨近于1.作為推論，對任意給定的α>1，αMOC-CDS都有PTAS近似算法.

1.6異質(zhì)無線傳感器網(wǎng)絡(luò)虛擬骨干近似算法

在異質(zhì)無線傳感器網(wǎng)絡(luò)(heterogeneous WSN)中，傳感器的傳輸半徑可能不同，此時，信息傳輸中會出現(xiàn)單向弧，網(wǎng)絡(luò)拓撲結(jié)構(gòu)可以模型化為一個有向圖，被稱為圓盤圖(disk graph)：每個傳感器u擁有一個傳輸半徑r(u)，圖中每個頂點對應(yīng)于平面上的一個傳感器，頂點u到頂點v有弧(u,v)相連的條件為‖uv‖≤r(u)，其中‖uv‖表示u,v兩點之間的歐氏距離.上述定義基于以下想法：當u,v兩點之間的距離不超過點u的傳輸半徑時，點v可以正確接收到點u發(fā)來的信息.也有研究者把異質(zhì)無線傳感器網(wǎng)絡(luò)模型化為無向圓盤圖(bidirectional disk graph)：u,v兩點之間連邊的條件是‖uv‖≤min{r(u),r(v)}.它基于如下想法：只有當2個傳感器都能正確接收彼此的信息時才認為它們之間通信正常.

對于無向圓盤圖，Thai等人在文獻[60]中給出了最小連通控制集的一個近似算法，其近似比依賴于最大傳輸半徑與最小傳輸半徑的比值R=rmaxrmin，當R有常數(shù)上界時是一個常數(shù)近似算法.該算法的思想類似于單位圓盤圖中最小連通控制集的處理，但傳輸半徑的差異帶來分析方法上的很大不同.其近似比分析的關(guān)鍵是最大獨立數(shù)α如何用最小連通控制集的點數(shù)γc去界定.Wang等人[61]通過更細致的幾何分析得到α≤(R*-1)γc+1，其中)2.進而給出無向圓盤圖中最小連通控制集問題的一個貪婪算法，其輸出解的點數(shù)不超過(R*+ln(R*-2)+1)γc+1.這是此方面目前最好的結(jié)果.

對于(有向)圓盤圖，其虛擬骨干則可以模型化為強連通控制吸收集(strongly connected dominating and absorbing set, SCDAS)：一個點u被點v控制，如果(v,u)是一條弧；一個點u被點v吸收，如果(u,v)是一條弧；一個點集C是控制吸收集，如果任意u∈VC都被C中至少一個點控制，也被C中至少一個點吸收(控制點與吸收點可能不同)；如果C的導出子圖強連通，則稱C為強連通控制吸收集.該模型保證了信息在全網(wǎng)絡(luò)的共享與互通.

Park等人在文獻[62]中給出了圓盤圖中最小強連通控制吸收集的一個近似算法，其思想同樣類似于單位圓盤圖的處理，近似比依賴于R=rmaxrmin.Li等人[63]在不對傳輸半徑做任何假設(shè)的條件下給出了最小強連通控制吸收集的(3H(n-1)-1)-近似算法.該算法從任一選定的節(jié)點u出發(fā)，借鑒了一般圖上最小權(quán)連通控制集蜘蛛分解的方法，得到一棵以u為根的出樹(out arborescence)和一棵以u為根的入樹(in arborescence)，這2棵樹的非葉子節(jié)點的并即構(gòu)成一個強連通控制吸收集.由于沒有利用任何幾何特性，該算法可以適用于任何有向圖的最小強連通控制吸收集問題.一個自然的問題是：圓盤圖中的最小強連通控制吸收集問題在不對傳輸半徑作任何假設(shè)的條件下是否存在常數(shù)近似算法？

該領(lǐng)域的研究在2009年取得一個較大的突破：Mustafa和Ray[64]用局域搜索的方法(local search)給出了一大類幾何圖形(包括半徑大小不同的圓盤)上的hitting set問題的PTAS近似算法.作為其推論，圓盤圖上的最小吸收集問題有PTAS近似.2010年，Gibson和Pirwani在文獻[65]中推廣了該方法，給出了(半徑大小不等的)圓盤相交圖(intersection graph of disks)中最小控制集問題的PTAS近似算法.運用其思想，可以得到圓盤圖上最小控制集問題的PTAS近似.兩者結(jié)合，圓盤圖上最小控制吸收集有(2+ε)-近似.進一步用蜘蛛分解的思想將其連接，Zhang等人在文獻[66]中得到最小強連通控制吸收集的一個(4+3ln(2+ε)opt+ε)-近似.注意到這仍然是一個對數(shù)級近似，只有當最優(yōu)值opt比傳感器數(shù)目小得多時才是對文獻[63]中近似比的一個改進.圓盤圖中最小強連通控制吸收集問題是否存在常數(shù)近似算法仍然是一個公開問題.

上述局域搜索算法非常有趣：簡潔而有效.以圓盤圖中最小吸收集問題為例，對于給定的常數(shù)b，吸收集U?V被稱為b-局域最優(yōu)解(b-locally optimal solution)，如果對任意階數(shù)不超過b的點集X?U和任意階數(shù)小于|X|的點集Y?VU，(UX)∪Y都不是吸收集，即：吸收集U無法通過不超過b個元素的局域搜索得到改進.算法以b-局域最優(yōu)解作為全局最優(yōu)解的近似.應(yīng)用著名的可平圖分離元定理(separator theorem of planar graph)，可以證明算法輸出解的點數(shù)不超過最優(yōu)解點數(shù)的1+O(1)倍，當b充分大時就構(gòu)成一個PTAS.

2研究方法小結(jié)與研究展望

2.1研究方法小結(jié)

綜上所述，在無線傳感器網(wǎng)絡(luò)虛擬骨干確定性近似算法的研究中被有效應(yīng)用的方法主要有以下3種:

1) 貪婪算法

貪婪算法基于眼前利益最大化的思想，是算法領(lǐng)域最基本的方法之一.但要能得到近似比分析，卻并不總是那么容易，其關(guān)鍵是要能定義一種合適的收益函數(shù)，使得每一步迭代中的收益量不會太小.例如：如果每一步迭代的收益至少是前一步迭代收益的常數(shù)倍，就可以得到對數(shù)級近似.特別地，當收益函數(shù)是單調(diào)不減的次模函數(shù)時，就滿足這一條件.然而，在連通控制集的相關(guān)研究中，很難構(gòu)造出單調(diào)不減的次模函數(shù)使得可行解可以在該函數(shù)值達到穩(wěn)定時取得.因此，針對具體問題，利用其特性構(gòu)造合適的收益函數(shù)成為該方面研究的關(guān)鍵.算法分析的另一個關(guān)鍵是要能在最優(yōu)解與貪婪解之間搭建一種橋梁.如Klein和Ravi在文獻[41]中提出的蜘蛛分解方法，在每一迭代步中都選取一個收益比最高的蜘蛛，通過把最優(yōu)解分解為蜘蛛的并，使最優(yōu)解與貪婪解具有了可比性.該方法對有向圖同樣有效，如有向網(wǎng)絡(luò)中強連通控制吸收集的近似算法[63].由于貪婪算法較少用到幾何性質(zhì)，故它往往可以用于一般圖中的算法設(shè)計與分析.

2) 劃分平移方法

劃分方法的思想基礎(chǔ)是“分而治之”，其關(guān)鍵是能夠?qū)栴}分解為若干部分，使得各部分能夠通過高階小量耦合起來.由于算法的主要損失發(fā)生在耦合部分，故希望耦合部分盡可能地小,利用平移是獲得這種高階小量的一種方法.運用劃分平移的方法，需要解決3個關(guān)鍵問題:①劃分后每個子問題如何求解？劃分思想的本質(zhì)就是縮減問題規(guī)模使之可以在多項式時間內(nèi)求解,但有的問題即使縮減了規(guī)模仍然很難求解，如加權(quán)問題.為子問題設(shè)計近似算法是一種解決方式.②如何將子問題的解拼接成原問題的解？如Cheng等人在文獻[16]中通過邊界區(qū)域與內(nèi)部區(qū)域一定程度的重迭保證了最終解的整體連通性.然而，如何去獲得更高階的整體連通性仍然是有待探索的問題.③分析中如何使最優(yōu)解與計算解之間具有可比性？一個自然的想法是把最優(yōu)解限制在子問題上，經(jīng)過一定的改造使之成為子問題的可行解,它依賴于如何合理定義子問題的可行解.劃分平移的方法被廣泛應(yīng)用于具有一定幾何特性的問題中，如可平圖、幾何交圖等.劃分方法還有很多有趣的變形，如多重網(wǎng)格劃分方法[67]、Guillotine割法[12]等，它們更適合于設(shè)計不規(guī)則問題的自適應(yīng)算法.

3) 局域搜索算法

局域搜索算法也是一個經(jīng)典的組合方法，它的思想是用局域最優(yōu)解來近似整體最優(yōu)解.Mustafa等人[64]將它成功地應(yīng)用于幾何覆蓋問題上，其橋梁是可平圖的分離元定理.該定理也是分而治之思想的體現(xiàn)，但在解決虛擬骨干問題時，它只用于近似比的分析而不是算法的實現(xiàn).對于各種具有幾何結(jié)構(gòu)的問題，是否存在類似的分離元定理是這類問題分析的關(guān)鍵，它與計算幾何學密切相關(guān).

除了上述方法之外，在研究虛擬骨干近似算法的過程中，還需要綜合應(yīng)用多種工具.如虛擬骨干的連通部分本質(zhì)上是個Steiner問題，Steiner領(lǐng)域的任何進展都有助于該問題的推進.目前Steiner問題最好的近似比大多基于線性規(guī)劃和隨機算法.又如容錯虛擬骨干的組合算法，目前主要使用連通度逐次提升的思想，它強烈依賴于高階連通圖的遞歸結(jié)構(gòu)，與圖論領(lǐng)域的研究密切相關(guān).由于無線傳感器網(wǎng)絡(luò)的幾何特性，幾何學更是廣泛地應(yīng)用于虛擬骨干近似算法的分析之中.例如目前很多算法的分析都基于圓盤圖中的獨立點集比較稀疏這一幾何性質(zhì).

2.2研究展望

在無線傳感網(wǎng)虛擬骨干近似算法的研究中，以下4個問題是長期懸而未決的，它們的解決需要更深的洞察力和理論上的創(chuàng)新.

1) 在不對傳輸半徑作任何假設(shè)的條件下，圓盤圖中最小強連通控制吸收集問題是否存在常數(shù)近似算法？我們已經(jīng)可以得到最小控制吸收集的(2+ε)-近似.該問題的難點在于強連通部分.可以證明，對于一個控制吸收集來說，距離最近的2個強連通分支之間3步可達,然而，方向性帶來本質(zhì)困難.可以構(gòu)造出圓盤圖G和控制吸收集C，加入2個點即可使C單向連通，但要使得C強連通，需要加入非常非常多的點.一個或許可行的思路是證明如果出現(xiàn)上述情況，則最優(yōu)解中一定也含有很多點.

2) 高維空間無向球圖(半徑可以不同)最小控制集問題是否存在PTAS近似算法？在平面上，該問題用局域搜索的方法可以得到PTAS.該方法成功的關(guān)鍵有2個:①可平圖的分離元定理;②滿足局域條件(locality condition)的可平圖的存在性.我們在文獻[68]中得到了d維空間無向球圖的分離元定理.然而，滿足局域條件的可平圖是否存在還是尚待回答的問題.

3) 一般圖中最小權(quán)連通控制集問題是否有比(1.35+ε)lnn更好的近似比？該近似比自1999年得到以來[40]，16年沒有任何改進.該算法運用了貪婪策略.很多與圖相關(guān)的貪婪算法，其近似比都具有O(lnΔ)的形式，其中Δ是圖的最大度.故上述近似比中的參數(shù)n能否改進到Δ，這是一個很有趣的問題.

4) 單位圓盤圖中是否存在關(guān)系

α≤3γc+3

(5)

事實上Vahdatpour等人[69]聲稱他們證明了這一關(guān)系,然而其證明并不嚴密(參見文獻[70]中的說明).Wan等人在文獻[23]中構(gòu)造了一個實例G，對該實例來說α(G)≥3γc(G)+3.故如果式(5)成立，則它將是緊的.

雖然本文對于以上問題提供了作者的一些初步思考，但它們的解決或許需要全新的思路，希望能引起讀者的興趣，集思廣益，在其解決過程中創(chuàng)造出新的方法和新的工具.

有學者還研究了具有最小直徑的虛擬骨干問題[71]、負載均衡的虛擬骨干問題[72-73]等.考慮虛擬骨干的多目標優(yōu)化問題是一個非常有趣的研究課題.在動態(tài)環(huán)境下研究虛擬骨干的維護算法是一個尚未充分展開的研究內(nèi)容[74].充分挖掘最小連通控制集問題的結(jié)論、理論、與方法在相關(guān)研究中的應(yīng)用也是研究者關(guān)注的一個重點.

參考文獻

[1]Akyildiz I F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114

[2]Tseng Y C, Ni S Y, Chen Y S, et al. The broadcast storm problem in a mobile ad hoc network[J]. Wireless Networks, 2002, 8(2): 153-167

[3]Ephremides A, Wieselthier J, Baker D. A design concept for reliable mobile radio networks with frequency hopping signaling[J]. Proceedings of the IEEE, 1987, 75(1): 56-73

[4]Garey M, Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: W.H. Freeman and Company, 1978

[5]Guha S, Khuller S. Approximation algorithms for connected dominating sets[J]. Algorithmica, 1998, 20(4): 374-387

[6]Kuhn F, Wattenhofer R, Zhang Y, et al. Geometric ad-hoc routing: Of theory and practice[C]Proc of the 22nd ACM Int Symp on the Principles of Distributed Computing. New York: ACM, 2003: 63-72

[7]Kuhn F, Wattenhofer R, Zollinger A. Asymptotically optimal geometric mobile ad-hoc routing[C]Proc of the 6th Int Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM’02). New York: ACM, 2002: 24-33

[8]Wang Yu, Li Xiangyang. Geometric spanners for wireless ad hoc networks[C]Proc of the 22nd Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2002: 171

[9]Berman P, Calinescu G, Shah C, et al. Power efficient monitoring management in sensor networks[C]Proc of IEEE Wireless Communication and Networking Conf (WCNC’04). Piscataway, NJ: IEEE, 2004: 2329-2334

[10]Du Dingzhu, Wan Pengjun. Connected Dominating Set: Theory and Applications[M]. Berlin: Springer, 2013

[11]Ruan Lu, Du Hongwei, Jia Xiaohua, et al. A greedy approximation for minimum connected dominating sets[J]. Theoretical Computer Science, 2004, 329(123): 325-330

[12]Du Dingzhu, Ko K I, Hu Xiaodong. Design and Analysis of Approximation Algorithms[M]. Berlin: Springer, 2012

[13]Zhu Xu, Yu Jieun, Lee Wonjun, et al. New dominating sets in social networks[J]. Journal of Global Optimization, 2010, 48(4): 633-642

[14]Du Dingzhu, Graham R, Pardalos P, et al. Analysis of greedy approximations with nonsubmodular potential functions[C]Proc of ACM-SIAM Symp on Discrete Algorithms (SODA’08). San Francisco, CA: ACM-SIAM, 2008: 167-175

[15]Clark B, Colbourn C, Johnson D. Unit disk graphs[J]. Discrete Mathematics, 1990, 86(123): 165-177

[16]Cheng Xiuzhen, Huang Xiso, Li Deying, et al. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks[J]. Networks, 2003, 42(2): 202-208

[17]Baker B. Approximation algorithms for NP-complete problems on planar graphs[C]Proc of the 24th Annual IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1983: 254-273

[18]Hochbaum D, Maass W. Approximation schemes for covering and packing problems in image processing and VLSI[J]. Journal of the ACM, 1985, 32(1): 130-136

[19]Zhang Zhao, Gao Xiaofeng, Wu Weili, et al. A PTAS for minimum connected dominating set in 3-dimiensional wireless sensor networks[J]. Journal of Global Optimization, 2009, 45(3): 451-458

[20]Wan Pengjun, Alzoubi K, Frieder O. Distributed construction of connected dominating set in wireless ad hoc networks[C]Proc of Int Conf on Computer Communications (INFOCOM’02). Piscataway, NJ: IEEE, 2002: 1597-1604

[21]Li Minming, Wan Pengjun, Yao Frances. Tighter approximation bounds for minimum CDS in wireless ad hoc networks[G]LNCS 5878: Proc of the 20th Int Symp on Algorithms and Computation (ISAAC 2009). Berlin: Springer, 2009: 699-709

[22]Gao Xiaofeng, Wang Yuexuan, Li Xianyue, et al. Analysis on theoretical bounds for approximating dominating set problems[J]. Discrete Mathematics, Algorithms and Applications, 2009, 1(1): 71-84

[23]Wan Pengjun, Wang Lixin, Yao Frances. Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks[C]Proc of the 28th IEEE Int Conf on Distributed Computing Systems (ICDCS 2008). Piscataway, NJ: IEEE, 2008: 337-344

[24]Wu Weili, Du Hongwei, Jia Xiaohua, et al. Minimum connected dominating sets and maximal independent sets in unit disk graphs[J]. Theoretical Computer Science, 2006, 352(13): 1-7

[25]Du Yingfan, Du Hongmin. A new bound on maximum independent set and minimum connected dominating set in unit disk graphs[J]. Journal of Combinatorial Optimization, doi:10.1007s10878-013-9690-0

[26]Li Jun, Gao Xiaofeng. An improved theoretical bound for minimum CDS in wireless ad hoc network[J]. Information, 2012, 15(12): 252-258

[27]Li Yingshu, Thai My, Wang Feng, et al. On greedy construction of connected dominating sets in wireless networks[J]. Wireless Communications and Mobile Computing, 2005, 5(8): 927-932

[28]Kim D, Zhang Zao, Li Xianyue, et al. A better approximation algorithm for computing connected dominating sets in unit ball graphs[J]. IEEE Trans on Mobile Computing, 2010, 9(8): 1108-1118

[29]Gao Xiaofeng, Li Jun, Chen Guihai. A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks[J]. Theoretical Computer Science, doi:10.1016j.tcs.2015.07.061

[30]Dai Fei, Wu Jie. On constructingk-connectedk-dominating set in wireless network[J]. Journal of Parallel and Distributed Computing, 2006, 66(7): 947-958

[31]Li Deying, Liu Lin, Yang Huiqiang. Minimum connectedr-hopk-dominating set in wireless networks[J]. Discrete Mathematics, Algorithms and Applications, 2009, 1(1): 45-57

[32]Zhang Zhao, Liu Qinghai, Li Deying. Two algorithms for connectedr-hopk-dominating set[J]. Discrete Mathematics, Algorithms and Applications, 2009, 1(4): 485-498

[33]Zhou Jiao, Zhang Zhao, Wu Weili, et al. A greedy algorithm for the fault-tolerant connected dominating set in a general graph[J]. Journal of Combinatorial Optimization, 2013, 28(1): 310-319

[34]Shi Yishuo, Zhang Yaping, Zhang Zhao, et al. A greedy algorithm for the minimum 2-connectedm-fold dominating set problem[J]. Journal of Combinatorial Optimization, doi:10.1007s10878-014-9720-6

[35]Zhang Zhao, Zhou Jiao, Mo Yuchang, et al. Performance-guaranteed approximation algorithm for fault-tolerant connected dominating set in wireless networks[C]Proc of Int Conf on Computer Communications (INFOCOM 2016). Piscataway, NJ: IEEE, 2016

[36]Wang Feng, Thai My, Du Dingzhu. On the construction of 2-connected virtual backbone in wireless networks[J]. IEEE Trans on Wireless Communications, 2009, 9(3): 1230-1237

[37]Shang Weiping, Yao Frances, Wan Pengjun, et al. On minimumm-connectedk-dominating set problem in unit disc graphs[J]. Journal of Combinatorial Optimization, 2008, 16(2): 99-106

[38]Kim D, Wang Wei, Li Xianyue, et al. A new constant factor approximation for computing 3-connectedm-dominating sets in homogeneous wireless networks[C]Proc of Int Conf on Computer Communications (INFOCOM’10). Piscataway, NJ: IEEE, 2010: 1-9

[39]Wang Wei, Liu Bei, Kim D, et al. A better constant approximation for minimum 3-connectedm-dominating set problem in unit disk graph using Tutte decomposition[C]Proc of Int Conf on Computer Communications (INFOCOM’15). Piscataway, NJ: IEEE, 2015: 1796-1804

[40]Guha S, Khuller S. Improved methods for approximating node weighted Steiner trees and connected dominating sets[J]. Information and Computation, 1999, 150(1): 57-74

[41]Klein P, Ravi R. A nearly best-possible approximation algorithm for node-weighted Steiner trees[J]. Journal of Algorithms, 1995, 19(1): 104-115

[42]Ambühl C, Erlebach T, Mihalák M, et al. Constant-factor approximation for minimum-weight (connect) dominating sets in unit disk graphs[G]LNCS 4110: Proc of the 9th Int Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006) and the 10th Int Workshop on Randomization and Computation (RANDOM 2006). Berlin: Springer, 2006: 3-14

[43]Huang Yaochun, Gao Xiaofeng, Zhang Zhao, et al. A better constant-factor approximation for weighted dominating set in unit disk graph[J]. Journal of Combinatorial Optimization, 2009, 18(2): 179-194

[44]Dai Decheng, Yu Changyuan. A (5+ε)-approximation algorithm for minimum weighted dominating set in unit disk graph[J]. Theoretical Computer Science, 2009, 410(8910): 756-765

[45]Zou Feng, Wang Yuexuan, Xu Xiaohua, et al. New approximations for weighted dominating sets and connected dominating sets in unit disk graphs[J]. Theoretical Computer Science, 2011, 412(3): 198-208

[46]Erlebach T, Mihalák M. A (4+ε)-approximation for the minimum-weight dominating set problem in unit disk graphs[G]LNCS 5893: Proc of the 7th Int Workshop Approximation and Online Algorithms (WAOA 2009). Berlin: Springer, 2010: 135-146

[47]Erlebach T, Grant T, Kammer F. Maximising lifetime for fault-tolerant target coverage in sensor networks[J]. Sustainable Computing: Informatics and Systems, 2011, 1(3): 213-225

[48]Willson J, Zhang Zhao, Wu Weili. Fault-tolerant coverage with maximum lifetime in wireless sensor networks[C]Proc of Int Conf on Computer Communications (NFOCOM’15). Piscataway, NJ: IEEE, 2015: 1364-1372

[49]Zou Feng, Li Xianyue, Gao Suogang, et al. Node-weighted Steiner tree approximation in unit disk graphs[J]. Journal of Combinatorial Optimization, 2009, 18(4): 342-349

[50]Byrka J, Grandoni F, Rothvoss T, et al. Steiner tree approximation via iterative randomized rounding[J]. Journal of the ACM, 2013, 60(1): 102-110

[51]Zhang Zhao, Shi Yishuo. Approximation algorithm for minimum weight fault-tolerant virtual backbone in homogeneous wireless sensor network[C]Proc of Int Conf on Computer Communications (INFOCOM’15). Piscataway, NJ: IEEE, 2015: 1080-1085

[52]Fleischer L. A 2-approximation for minimum cost {0,1,2} vertex connectivity[C]Proc of the 8th Int Conf on Integer Programming and Combinatorial Optimization (IPCO 2001). Utrecht, the Netherlands: Mathematical Optimization Society, 2001: 115-129

[53]Ding Ling, Gao Xiaofeng, Wu Weili, et al. Distributed construction of connected dominating sets with minimum routing cost in wireless network[C]Proc of the 30th Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2010: 448-457

[54]Ding Ling, Wu Weili, Willson J, et al. Efficient algorithms for topology control problem with routing cost constraint in wireless networks[J]. IEEE Trans on Parallel Distributed Systems, 2011, 22(10): 1601-1607

[55]Du Hongwei, Ye Qiang, Wu Weili, et al. Constant approximation for virtual backbone construction with guaranteed routing cost in wireless sensor networks[C]Proc of INFOCOM’11. Piscataway, NJ: IEEE, 2011: 1737-1744

[56]Du Hongwei, Wu Weili, Lee Wongjun, et al. On minimum submodular cover with submodular cost[J]. Journal of Global Optimization, 2011, 50(2): 229-234

[57]Du Hongwei, Ye Qiang, Zhong Jiaofei, et al. PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks[G]LNCS 6508: Proc of the 4th Annual Int Conf on Combinatorial Optimization and Applications (COCOA 2010). Berlin: Springer, 2010: 252-259

[58]Liu Qinghai, Zhang Zhao, Hong Yanmei, et al. A PTAS for weak minimum routing cost connected dominating set of unit disk graph[C]Proc of 2013 Optimization, Simulation, and Control. Berlin: Springer, 2013: 131-142

[59]Liu Qinghai. Algorithms for same combinatorial optimization problems[D]. Urumqi: Xinjiang University, 2012 (in Chinese)(劉清海. 幾類組合優(yōu)化問題的算法研究[D]. 烏魯木齊: 新疆大學, 2012)

[60]Thai My, Wang Feng, Liu Dan, et al. Connected dominating sets in wireless networks with different transmission ranges[J]. IEEE Trans on Mobile Computing, 2007, 6(1): 721-730

[61]Wang Linxin, Wan Pengjun, Yao Frances. Minimum CDS in multihop wireless networks with disparate communication ranges[J]. IEEE Trans on Mobile Computing, 2013, 12(5): 909-916

[62]Park M, Wilson J, Wang Chen, et al. A dominating and absorbent set in a wireless ad-hoc network with different transmission range[C]Proc of MobiHoc 2007. New York: ACM, 2007: 22-31

[63]Li Deying, Du Hongwei, Wan Pengjun, et al. Construction of strongly connected dominating sets in asymmetric multihop wireless networks[J]. Theoretical Computer Science, 2009, 410(8910): 661-669

[64]Mustafa N, Ray S. PTAS for geometric hitting set problems via local search[C]Proc of Symp on Computational Geometry (SOCG 2009). New York: ACM, 2009: 17-22

[65]Gibson M, Pirwani I. Algorithms for dominating set in disk graphs: Breaking the lognbarrier[G]LNCS 6346: Proc of the 18th Annual European Symp, Algorithms (ESA 2010). Berlin: Springer, 2010: 243-254

[66]Zhang Zhao, Wu Weili, Wu Lidong, et al. Strongly connected dominating and absorbing set in directed disk graph[J]. International Journal of Sensor Networks, 2015, 19(2): 69-77

[67]Erlebach T, Jansen K, Seidel E. Polynomial-time approximation schemes for geometric intersection graphs[J]. SIAM Journal of Computing, 2005, 34(6): 1302-1323

[68]Zhang Zhao, Wu Weili, Fan Lidan, et al. Minimum vertex cover in ball graphs through local search[J]. Journal of Global Optimization, 2014, 59(2): 663-671

[69]Vahdatpour A, Dabiri F, Moazeni M, et al. Theoretical bound and practical analysis of connected dominating set in ad hoc and sensor networks[C]Proc of the 22nd Int Symp on Distributed Computing (DISC 2008). Berlin: Springer, 2008: 481-495

[70]Zhang Zhao, Wu Weili, Ding Ling, et al. Packing Circles in Circles and Applications, Handbook of Combinatorial Optimization[M]. 2nd ed. Pardalos P M, Du Dingzhu, Graham R L, eds. Berlin: Springer, 2013: 2549-2584

[71]Kim D, Wu Yiwei, Li Yingshu, et al. Constructing minimum connected dominating sets with bounded diameters in wireless networks[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20(2): 147-157

[72]He Jing, Ji Shuoling, Pan Yi, et al. Greedy construction of load-balanced virtual backbones in wireless sensor networks[J]. Wireless Communications & Mobile Computing, 2014, 14(7): 673-688

[73]He Jing, Ji Shuoling, Pan Yi, et al. Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks[J]. Theoretical Computer Science, 2013, 507: 2-16

[74]Qin Yunlong, Yu Jiguo, Wang Kang. A maintaining algorithm fork-connectedm-dominating sets in wireless mobile networks[J]. Computer Technology and Development, 2010, 20(8): 83-86 (in Chinese)(秦云龍, 禹繼國, 王康. 無線移動網(wǎng)絡(luò)中k連通m控制集的一個維護算法[J]. 計算機技術(shù)與發(fā)展, 2010, 20(8): 83-86)

Zhang Zhao, born in 1974. Received her PhD from Xinjiang University in 2003. Professor in Zhejiang Normal University. Member of China Computer Federation. Her current research interests include the design and analysis of approximation algorithms for optimization problems in networks.

中圖法分類號TP301.6

基金項目：國家自然科學基金項目(61222201,11531011)；教育部高等學校博士學科點專項科研基金項目(20126501110001)；新疆杰出青年科技人才培養(yǎng)項目(2013711011)

收稿日期：2015-07-15；修回日期：2015-10-06

This work was supported by the National Natural Science Foundation of China (61222201,11531011), Research Fund for the Doctoral Program of Higher Education of China (20126501110001), and Excellent Youth Foundation of Xinjiang Scientific Committee (2013711011).