張　昭

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

(hxhzz@sina.com)

?

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

張昭

(浙江師范大學(xué)浙江金華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ú)線傳感器網(wǎng)絡(luò)中應(yīng)用虛擬骨干，可以有效地節(jié)約能量、減少干擾、延長(zhǎng)網(wǎng)絡(luò)壽命，在幾何路由算法和網(wǎng)絡(luò)拓?fù)淇刂频确矫婢哂袕V泛的應(yīng)用.虛擬骨干可以模型化為圖中的連通控制集.主要從近似算法角度介紹連通控制集及其各種變形在國(guó)內(nèi)外的研究現(xiàn)狀及最新進(jìn)展，側(cè)重于研究方法和理論結(jié)果，為相關(guān)研究人員提供參考.

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

1.2單位圓盤(pán)圖上連通控制集的近似算法

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

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

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

1.3容錯(cuò)連通控制集的近似算法

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

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

Table 1　Current Results for Fault-Tolerant CDS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

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

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

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

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

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

(4)

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

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

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

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

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

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

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

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

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

2.1研究方法小結(jié)

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

1) 貪婪算法

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

2) 劃分平移方法

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

3) 局域搜索算法

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

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

2.2研究展望

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

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

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

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

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

α≤3γc+3

(5)

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

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

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

參考文獻(xià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)(劉清海. 幾類(lèi)組合優(yōu)化問(wèn)題的算法研究[D]. 烏魯木齊: 新疆大學(xué), 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)(秦云龍, 禹繼國(guó), 王康. 無(wú)線移動(dòng)網(wǎng)絡(luò)中k連通m控制集的一個(gè)維護(hù)算法[J]. 計(jì)算機(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.

中圖法分類(lèi)號(hào)TP301.6

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61222201,11531011)；教育部高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金項(xiàng)目(20126501110001)；新疆杰出青年科技人才培養(yǎng)項(xià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).