无线传感器网络虚拟骨干近似算法综述

张　昭

(浙江师范大学　浙江金华　321004)

(hxhzz@sina.com)



无线传感器网络虚拟骨干近似算法综述

张昭

(浙江师范大学浙江金华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

摘要在无线传感器网络中应用虚拟骨干，可以有效地节约能量、减少干扰、延长网络寿命，在几何路由算法和网络拓扑控制等方面具有广泛的应用.虚拟骨干可以模型化为图中的连通控制集.主要从近似算法角度介绍连通控制集及其各种变形在国内外的研究现状及最新进展，侧重于研究方法和理论结果，为相关研究人员提供参考.

关键词无线传感器网络；虚拟骨干；连通控制集；近似算法；近似比

无线传感器网络(wireless sensor network, WSN)是一种分布式的传感网络，它由大量可以感知外部世界的传感器组成，并通过无线通信方式形成一个多跳的自组织网络.无线传感器网络在军事和民用等领域具有广泛的应用，如战场监控、环境监测、交通监管、智能家居、医疗卫生等[1].由于无线传感器网络没有固定的基础设施，传感器主要以自组织和多跳的方式协作地完成信息的传输和共享，故如何有效地进行拓扑控制和路由选择以获得一个高效、可靠、节能的自组织网络是一个具有挑战性的课题.如果信息传输过程使用简单的洪泛(flooding)方式(即每个传感器将它所感知的信息立即播报出去)，则极易造成能量的耗费并产生大量的信号干扰，引起广播风暴(broadcast storm)[2].文献[3]研究表明：在无线传感器网络中引入虚拟骨干(virtual backbone)，可以有效地减少信息传输过程中的拥堵、极大地提高能量的使用率、延长网络的寿命.

虚拟骨干可以模型化为图论中的连通控制集(connected dominating set, CDS).给定图G=(V,E)，顶点V的子集C称为控制集，如果VC中的每个顶点都在C中有邻点.进一步，如果由C导出的子图G[C]是连通的，则称C为连通控制集.计算最小连通控制集是经典的NP-难问题[4].因此，人们更感兴趣的是如何对它设计有近似比(performance ratio)保证的多项式时间近似算法.事实上，Guha和Khuller在文献[5]中构造了一个从最小集合覆盖问题(minimum set cover)到最小连通控制集问题的保近似的约化(approximation preserving reduction)，因此，最小连通控制集问题是SC-难的.这意味着：除非NP⊆DTIME(nO(loglog n))，否则对任意0<ρ<1，最小连通控制集问题不存在近似比可以达到ρlnn的多项式时间近似算法.然而，利用无线传感器网络的特殊性质，有可能得到该问题的更好近似.另外，人们希望虚拟骨干具有各种良好的性质，因此，连通控制集的各种变形也成为国际相关研究的热点之一.

研究连通控制集及其各种变形的近似算法，不仅是研究虚拟骨干自身的需要，还是其它相关研究的基础.

例如在几何路由(geometric routing)的局域算法(local algorithm)中，Kuhn等人[6]给出了一个GOAFR+算法，并证明了对于具有有界度(bounded degree)的单位圆盘图(unit disk graph, UDG)，该算法可以得到一个长度不超过O(c2)的路径，其中c为最优路径长度.文献[7]指出，O(c2)是局域路由算法所能企及的最好可能.但对于度数无常数界的单位圆盘图来说，该算法质量无法保证.为了解决这个问题，Wang等人在文献[8]中设计了一个推广GOAFR+算法.该算法先构造了一个具有有界度的连通控制集作为路由骨干网，再在这个路由骨干网上应用GOAFR+算法就可以得到上述渐近最优的路径长度.

又如无线传感器网络覆盖的最大生命期问题(maximum lifetime of coverage)中，人们希望通过对传感器工作睡眠状态的控制来实现网络生命期的最大化.Berman等人[9]发现，该问题可以转化为一系列最小权连通控制集问题来求解，如果最小权连通控制集问题有多项式时间ρ-近似算法，则最大生命期问题就存在多项式时间(ρ+ε)-近似算法，其中ε是任意一个大于0的实数.

事实上，一个好的连通控制集可以反映出网络的主要特征，借助它去实现整个网络的功能可以取得更好的产出比.因此，如何构建一个好的连通控制集是一个很有意义的课题.

本文旨在综述最小连通控制集问题及其主要变形的发展现状，侧重于确定性算法的主要研究方法和理论结果，并对主要研究方法做一个小结，对相关研究方向的发展做一个展望.

1虚拟骨干近似算法研究现状

近年来，由于无线传感器网络的兴起，连通控制集问题及其各种变形引起国际同行的广泛研究.Du和Wan在文献[10]中对各种与连通控制集相关的算法问题给出了详细的方法性论述.本文对连通控制集近似算法方面的研究现状和研究方法作概要性的介绍，以期为相关研究人员提供一个总体性的参考.

1.1一般图上连通控制集的近似算法

Ruan等人在文献[11]中又给出了最小连通控制集的一个(2+lnΔ)-近似算法.虽然该近似比只比前者改进了一点点，但在研究方法上却有一个新的突破.事实上，很多问题的贪婪算法都可以用势函数(potential function)来描述：设A,B是2个集合，势函数f(A)表示集合A的收益，差分ΔBf(A)=f(A∪B)-f(A)表示在A的基础上增加B中元素后新增的收益(或称边际效益(marginal profit))；贪婪策略从A=∅开始，迭代地选择元素x加入A，使得Δxf(A)最大；直至对任意x都有Δxf(A)=0时(称为终止准则)，算法终止.称势函数f为单调增函数，如果对任意的A⊆B，都有f(A)≤f(B).称势函数f为次模函数，如果对任意的A⊆B和任意的集合C，都有:

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

(1)

即f满足边际效益递减律.经典理论表明，如果势函数是单调增的次模函数且f(∅)=0，则贪婪算法的近似比不超过H(γ)，其中γ=max{f(x)}[12].遗憾的是，对于最小连通控制集问题，同时满足终止准则和次模性要求的势函数一直未能找到.Ruan等人的贡献在于，他们发现算法分析中只需要式(1)对一些与最优解和贪婪解相关的特定集合成立即可(并不需要对任何集合A,B,C都成立)，甚至当式(1)右端减去一个常数c时都可以得到对数级近似.具体来说，他们构造了一种非次模势函数f.假设Ag={x1,x2,…,xg}为贪婪算法的输出解，其中元素x1,x2,…,xg按贪婪算法选择它们的顺序排列.对i=1,2,…,g，记Ai={x1,x2,…,xi}.又设B={y1,y2,…,ym}为最优解.对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)

应用式(2)他们得到了最小连通控制集的(2+lnΔ)-近似.该方法突破了传统贪婪算法次模性的要求，被广泛应用于后续工作中，包括社会网络中最小种子(seed)集合的选择问题等[13].Du等人在文献[14]中又进一步研究了该方法的变形，给出了最小连通控制集的一个(1+ε)ln(Δ-1)-近似算法，其中ε是任意正实数.

1.2单位圆盘图上连通控制集的近似算法

单位圆盘图(UDG)是均质无线传感器网络(homogeneous WSN)中普遍采用的一种数学模型：图中每个点对应于平面上的一个传感器，2个点在图中相邻的充要条件是相应传感器之间的欧氏距离不超过1(单位长度).Clark等人[15]证明：即使局限到单位圆盘图中，最小连通控制集问题仍然是NP-困难的.然而，利用单位圆盘图的几何性质，该问题可以得到较好的近似比.

Cheng等人在文献[16]中给出了单位圆盘图中最小连通控制集的第1个多项式时间近似方案(polynomial time approximation scheme, PTAS)，即在(与ε相关的)多项式时间内逼近最优解的精度可以达到1+ε.该算法以划分平移方法(technique of partition and shifting)为框架.划分是“分而治之”思想的体现：把众多小区域上的解组装起来得到大区域上的解.组装过程中会产生一定的损失，损失主要发生在小区域的边界地带.当小区域尺寸足够大时，在概率意义下边界会相对很“薄”，从而损失会是一个ε小量.平移技巧正是这种概率思想确定性的实现.划分平移方法是近似算法中的一个经典的手段[17-18].对于最小连通控制集来说，应用该方法的难点在于连通性的处理.Cheng等人首次提出了内部区域和边界区域的概念，其算法在得到各内部区域在一定意义下的最优解后，迭加一个常数近似算法落在边界区域中的点集，通过内部区域与边界区域一定程度的重合，保证了算法输出解的连通性要求.但该算法的分析无法推广到高维空间中，因为其分析中用到了平面上的2条直线不平行则相交这一性质.Zhang等人在文献[19]中引入了新的分析技巧，将该PTAS近似算法推广至任意维空间的单位球图(unit ball graphs, UBG)上，其关键是一种“微小补偿”的思想.具体来说，为了得到最优解与算法输出解之间的一个比较，需要考虑最优解在每个小区域上的限制，并将它改造成为小区域上具有给定意义的可行解.该算法分析在改造过程中加入了一些新的点，并证明了所加的点数可以被最优解落在边界区域中的点数所控制，结合平移技巧，后者是一个ε小量(微小补偿).

PTAS的近似比较小，但计算时间太长.为此，有必要探索时间复杂度较低的分布式算法.该方面最初的研究是由Wan等人[20]给出的，他们先通过对一棵广度优先搜索树的顶点进行着色，得到一个具有如下性质的极大独立集(maximal independent set)：如果将该极大独立集任意划分成2部分，这2部分之间距离最近的2个点都是2-步可达的.基于这一性质，最多加一个点就可以融合至少2个分支，从而连通它们所加的点数不超过独立点数.因此，要得到近似比分析，就要估计最大独立数α与最小连通控制集的点数γc之间的关系.Wan等人证明了：在单位圆盘图中，α≤4γc+1，从而他们的算法近似比不超过8.这方面的研究与几何中的packing问题密切相关，即给定区域中最多可以装入多少个独立点.经过一系列的改进[21-26]，应用了大量几何工具，包括Voronoi digram、欧拉公式等，目前该关系方面最好的界[26]为α≤3.3371γc+3.6741.另一个改进近似比的方向是减少连接部分所加的点数.Li等人[27]运用最小点数Steiner树的思想构造了一个近似算法，贪婪地用最大度点去融合连通分支，通过利用单位圆盘图中每个点最多与5个分支相邻这一事实，他们证明了该算法连接部分所用的点数不超过最优解点数的(2+ln 4)≈2.4倍.Kim等人在文献[28]中运用类似的思想给出了3维单位球图中最小连通控制集的一个分步式近似算法，其近似比为14.937，但在分析中有一个错误.Gao等人在文献[29]中提出了一种新的投影方法纠正了这一错误.这方面研究的难点在于高维空间中packing问题的几何分析.

1.3容错连通控制集的近似算法

在实际应用中，无线传感器网络往往具有很强的动态性，网络的拓扑结构经常会由于能量耗尽或元件故障而发生改变.因此，人们希望虚拟骨干具有一定的容错性(fault-tolerance)，即在部分传感器出现故障的情况下整个网络仍能正常通信的能力.该问题可模型化为最小k-连通m-重控制集问题(简称(k,m)-CDS问题)，即要求虚拟骨干C以外的任一点都至少被C中m个点所控制，而C导出的子图的连通度至少为k.采用(k,m)-CDS作为虚拟骨干，即使min{k-1,m-1}个节点发生故障，虚拟骨干仍能正常工作.

Dai和Wu在2005年最先将最小(k,m)-CDS问题引入容错虚拟骨干的研究中[30]，并给出了最小(k,k)-CDS的3个启发式算法，但没有给出近似比分析.表1总结了该研究领域中有近似比保证的主要研究结果.由于只总结与容错性相关的结果，故表1的k和m中至少有一个大于1.

Table 1　Current Results for Fault-Tolerant CDS

对于单位圆盘图，Wang等人在文献[36]中给出了(2,1)-CDS的一个72-近似算法.该算法提出了一种把连通控制集的连通度提升到2的方法：利用1-连通但非2-连通图的块分解(block decompostion)结构(块是极大的无割点的子图)，不断地用联结不同块的最短路去融合块，直到得到一个2-连通图.该算法近似比分析中的关键是：在连通度达到2之前，总存在一条可以融合块的路，其长度不超过9，从而把连通度由1提升到2的过程中所加的点数不超过(1,1)-CDS的8倍.

Shang等人在文献[37]中提出了一种在单位圆盘图中寻找m-重控制集的方法：迭代地选取m个极大独立集，它们的并即构成一个m-重控制集.利用单位圆盘图中的独立点比较稀疏这一性质，Shang等人给出了单位圆盘图中(1,m)-CDS的常数近似算法，并进一步运用Wang等人提升连通度的方法[36]，得到了m≥2时单位圆盘图中(2,m)-CDS的常数近似算法.注意到m≥2时，每步迭代中最多增加2个点就可以减少块的个数.在这种条件下，把连通度由1提升到2的过程中所加的点数不超过(1,1)-CDS的2倍.

Kim等人在文献[38]中得到了单位圆盘图中最小(3,m)-CDS问题的常数近似算法，但该算法非常复杂，近似比也很大，如(3,3)-CDS的近似比为280.Wang等人于2015年在文献[39]中运用2-连通但非3-连通图的Tutte-分解简化了该算法，并改进了近似比.特别地，(3,3)-CDS的近似比可以降到62.3.

对于一般图，Zhou等人在文献[33]中设计了一个非次模的势函数，给出了(1,m)-CDS的一个贪婪算法，其近似比不超过2+H(Δ+m-2).考虑到最小(k,m)-CDS问题的不可ρlnn-近似性，该近似比达到了渐近最优.以此为基础，Shi等人在文献[34]中利用块分解结构将连通度由1提升到了2.与文献[36-37]不同的是，文献[34]以块的个数为势函数，用贪婪策略选择所加的路，注意到块的个数并不是次模函数.但是，文献[34]找到了最优解的一种分解结构，导出了其元素的一种排列方式，证明了与式(2)具有相似味道的一个不等式，从而在m≥2的条件下得到了一般图中(2,m)-CDS的渐近最优的近似算法.将它应用到单位圆盘图中，可以改进Shang等人[37]中的近似比.

基于Tutte分解，我们用非次模势函数的方法，在m≥3的条件下得到了一般图中最小(3,m)-CDS的一个渐近最优的近似算法.特别地，将它应用到单位圆盘图上，∀m≥3，近似比都不超过27.

1.4最小权连通控制集的近似算法

在一般图中，Guha和Khuller在文献[40]中给出了一个近似比不超过(1.35+ε)lnn的近似算法.该结果是最小点加权Steiner树问题的一个应用.Klein和Ravi在文献[41]中首先提出了一种蜘蛛分解的方法(spider decomposition)，得到了最小点加权Steiner树问题的2ln |R|-近似，其中R为Steiner树问题的终端集合(terminal set).Guha和Khuller在文献[40]中将上述方法推广到分支蜘蛛分解(branch spider decomposition)，进而把近似比改进为(1.35+ε)ln |R|.特别地，取R=V，可以得到最小权连通控制集的(1.35+ε)lnn-近似.该结果于1999年得到，至今一直没有得到改进.

单位圆盘图中最小权连通控制集的第1个常数近似算法由Ambühl等人在文献[42]中给出.他们首先提出了一个特殊的覆盖问题：从一些圆心在某水平带子之外的圆盘中选择一部分去覆盖分布在水平带子中的点，目标是所选圆盘的总权重最小.Ambühl等人设计了一种动态规划算法，在多项式时间内可以得到该问题的最优解;然后，他们将单位圆盘图中的最小权控制集问题分解为一系列水平带子覆盖问题和垂直带子覆盖问题，得到最小权控制集问题的一个72-近似;最后，再将所得控制集连通起来，其连通部分的近似比为17.

Huang等人在文献[43]中引入了双重划分(double-partition)的技巧，将上述控制部分和连通部分的近似比分别降低到了6+ε和4.该算法在求解控制集阶段的思想是：将尽可能多的带子覆盖问题综合起来求解，以减少最优解中每个圆盘所使用的重复度.算法的关键是如何分解原问题，使得分解出来的子问题与原问题相容，即原问题的最优解能够成为子问题的可行解，同时还必须保证分解得到的子问题数目不超过原问题规模的多项式.为此，文献[43]提出了一个“沙漏”(sand glass)的几何概念，应用它简化了分解问题的复杂度，使得算法可以在多项式时间内完成.该算法在连通阶段的思想是：把问题转化为边加权最小支撑树问题，运用单位圆盘中每个点最多有5个相邻分支这一事实，证明了最优解中每个点被重复利用的次数不超过4，从而得到连通部分的4-近似.

上述思想被进一步深化.Dai和Yu在文献[44]中将求解单位圆盘图中最小权控制集的近似比改进到5+ε，该近似比又被Zou等人[45]和Erlebach与Mihalák[46]改进到4+ε.这些改进均基于对动态规划算法的改进，即不再是一条带子一条带子地分别求解，而是将具有相同奇偶性标号的带子综合起来求解，从而进一步节省了最优解中每个圆盘被使用的重复度.

推广上述思想，Erlebach等人在文献[47]中得到了单位圆盘图中最小权2-重控制集问题的一个(6+ε)-近似算法.Zhang等人在文献[48]中对任意正整数m，得到了单位圆盘图中最小权m-重控制集问题的(4+ε)-近似.为此，文献[48]首先提出了一个最小权奇偶带子多重覆盖问题(minimum weight parity strip multi-cover)，证明了该问题可以用动态规划在多项式时间内求解;然后将原问题分解为4个最小权奇偶带子多重覆盖问题，从而得到该问题的(4+ε)-近似.文献[48]引入了钻石(diamond)和楔(wedge)等几何概念，解决了问题分解的相容性和多项式时间可实现性等难点.

应用Steiner树的思想，最小权连通控制集连通部分的近似比可以降低到Δρ2，其中ρ为最小边权Steiner树问题的近似比，Δ为图的最大度.事实上，对每条边uv赋以权值(w(u)+w(v))2，就可以把点赋权的问题转化为边赋权的问题，而每个点的权在最小边权Steiner树的求解中被重复利用的次数不超过Δ2.Zou等人[49]注意到：任何一个连通的单位圆盘图中都存在一个连通的支撑子图，其最大度不超过5.结合目前已知最好的ρ值1.39[50]，单位圆盘图中最小权控制集问题连通部分的近似比不超过3.475.

Zhang等人在文献[51]中研究了最小权k-连通m-重控制集问题，通过证明任意2-连通的单位圆盘图中都存在一个2-连通支撑子图，其最大度不超过5，并利用最小权{0,1,2}-Steiner树问题的2-近似算法[52]，最小权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两点的中间节点全在C中的最短路长度.连通控制集C称为MOC-CDS，如果

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

(3)

Ding等人证明了MOC-CDS是SC-难问题，并给出了一个H(Δ(Δ-1)2)-近似算法.该算法的关键一步是证明了式(3)等价于：对任意距离恰为2的u,v点都有

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

从而可以把MOC-CDS的求解转化为一个最小集合覆盖问题，再应用最小集合覆盖问题的贪婪算法即得上述近似比.

数值实验显示MOC-CDS的尺寸非常大[53].为了平衡虚拟骨干的尺寸和路由费用，Ding等人[54]又提出了αMOC-CDS的概念：对于给定的常数α≥1，任意u,v点都满足：

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

这里的α对应于计算几何中的拉伸因子(stretch factor).对于α≥5，Du等人给出了单位圆盘图中αMOC-CDS的常数近似算法[55-56]，并进一步运用划分平移的思想给出了PTAS[57].

一个自然的问题是α<5时会如何?Liu等人在文献[58-59]中部分地回答了该问题.定义gMOC-CDS为一个满足如下条件的连通控制集C：对给定的常数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之间都添加一条最短路，可以证明该算法具有常数近似比.进一步，运用划分平移的方法，可以得到gMOC-CDS的PTAS.注意到k=1时式(4)中的乘法因子1+4k=5，当k增大时该乘法因子单调递减趋近于1.作为推论，对任意给定的α>1，αMOC-CDS都有PTAS近似算法.

1.6异质无线传感器网络虚拟骨干近似算法

在异质无线传感器网络(heterogeneous WSN)中，传感器的传输半径可能不同，此时，信息传输中会出现单向弧，网络拓扑结构可以模型化为一个有向图，被称为圆盘图(disk graph)：每个传感器u拥有一个传输半径r(u)，图中每个顶点对应于平面上的一个传感器，顶点u到顶点v有弧(u,v)相连的条件为‖uv‖≤r(u)，其中‖uv‖表示u,v两点之间的欧氏距离.上述定义基于以下想法：当u,v两点之间的距离不超过点u的传输半径时，点v可以正确接收到点u发来的信息.也有研究者把异质无线传感器网络模型化为无向圆盘图(bidirectional disk graph)：u,v两点之间连边的条件是‖uv‖≤min{r(u),r(v)}.它基于如下想法：只有当2个传感器都能正确接收彼此的信息时才认为它们之间通信正常.

对于无向圆盘图，Thai等人在文献[60]中给出了最小连通控制集的一个近似算法，其近似比依赖于最大传输半径与最小传输半径的比值R=rmaxrmin，当R有常数上界时是一个常数近似算法.该算法的思想类似于单位圆盘图中最小连通控制集的处理，但传输半径的差异带来分析方法上的很大不同.其近似比分析的关键是最大独立数α如何用最小连通控制集的点数γc去界定.Wang等人[61]通过更细致的几何分析得到α≤(R*-1)γc+1，其中)2.进而给出无向圆盘图中最小连通控制集问题的一个贪婪算法，其输出解的点数不超过(R*+ln(R*-2)+1)γc+1.这是此方面目前最好的结果.

对于(有向)圆盘图，其虚拟骨干则可以模型化为强连通控制吸收集(strongly connected dominating and absorbing set, SCDAS)：一个点u被点v控制，如果(v,u)是一条弧；一个点u被点v吸收，如果(u,v)是一条弧；一个点集C是控制吸收集，如果任意u∈VC都被C中至少一个点控制，也被C中至少一个点吸收(控制点与吸收点可能不同)；如果C的导出子图强连通，则称C为强连通控制吸收集.该模型保证了信息在全网络的共享与互通.

Park等人在文献[62]中给出了圆盘图中最小强连通控制吸收集的一个近似算法，其思想同样类似于单位圆盘图的处理，近似比依赖于R=rmaxrmin.Li等人[63]在不对传输半径做任何假设的条件下给出了最小强连通控制吸收集的(3H(n-1)-1)-近似算法.该算法从任一选定的节点u出发，借鉴了一般图上最小权连通控制集蜘蛛分解的方法，得到一棵以u为根的出树(out arborescence)和一棵以u为根的入树(in arborescence)，这2棵树的非叶子节点的并即构成一个强连通控制吸收集.由于没有利用任何几何特性，该算法可以适用于任何有向图的最小强连通控制吸收集问题.一个自然的问题是：圆盘图中的最小强连通控制吸收集问题在不对传输半径作任何假设的条件下是否存在常数近似算法？

该领域的研究在2009年取得一个较大的突破：Mustafa和Ray[64]用局域搜索的方法(local search)给出了一大类几何图形(包括半径大小不同的圆盘)上的hitting set问题的PTAS近似算法.作为其推论，圆盘图上的最小吸收集问题有PTAS近似.2010年，Gibson和Pirwani在文献[65]中推广了该方法，给出了(半径大小不等的)圆盘相交图(intersection graph of disks)中最小控制集问题的PTAS近似算法.运用其思想，可以得到圆盘图上最小控制集问题的PTAS近似.两者结合，圆盘图上最小控制吸收集有(2+ε)-近似.进一步用蜘蛛分解的思想将其连接，Zhang等人在文献[66]中得到最小强连通控制吸收集的一个(4+3ln(2+ε)opt+ε)-近似.注意到这仍然是一个对数级近似，只有当最优值opt比传感器数目小得多时才是对文献[63]中近似比的一个改进.圆盘图中最小强连通控制吸收集问题是否存在常数近似算法仍然是一个公开问题.

上述局域搜索算法非常有趣：简洁而有效.以圆盘图中最小吸收集问题为例，对于给定的常数b，吸收集U⊆V被称为b-局域最优解(b-locally optimal solution)，如果对任意阶数不超过b的点集X⊆U和任意阶数小于|X|的点集Y⊆VU，(UX)∪Y都不是吸收集，即：吸收集U无法通过不超过b个元素的局域搜索得到改进.算法以b-局域最优解作为全局最优解的近似.应用著名的可平图分离元定理(separator theorem of planar graph)，可以证明算法输出解的点数不超过最优解点数的1+O(1)倍，当b充分大时就构成一个PTAS.

2研究方法小结与研究展望

2.1研究方法小结

综上所述，在无线传感器网络虚拟骨干确定性近似算法的研究中被有效应用的方法主要有以下3种:

1) 贪婪算法

贪婪算法基于眼前利益最大化的思想，是算法领域最基本的方法之一.但要能得到近似比分析，却并不总是那么容易，其关键是要能定义一种合适的收益函数，使得每一步迭代中的收益量不会太小.例如：如果每一步迭代的收益至少是前一步迭代收益的常数倍，就可以得到对数级近似.特别地，当收益函数是单调不减的次模函数时，就满足这一条件.然而，在连通控制集的相关研究中，很难构造出单调不减的次模函数使得可行解可以在该函数值达到稳定时取得.因此，针对具体问题，利用其特性构造合适的收益函数成为该方面研究的关键.算法分析的另一个关键是要能在最优解与贪婪解之间搭建一种桥梁.如Klein和Ravi在文献[41]中提出的蜘蛛分解方法，在每一迭代步中都选取一个收益比最高的蜘蛛，通过把最优解分解为蜘蛛的并，使最优解与贪婪解具有了可比性.该方法对有向图同样有效，如有向网络中强连通控制吸收集的近似算法[63].由于贪婪算法较少用到几何性质，故它往往可以用于一般图中的算法设计与分析.

2) 划分平移方法

划分方法的思想基础是“分而治之”，其关键是能够将问题分解为若干部分，使得各部分能够通过高阶小量耦合起来.由于算法的主要损失发生在耦合部分，故希望耦合部分尽可能地小,利用平移是获得这种高阶小量的一种方法.运用划分平移的方法，需要解决3个关键问题:①划分后每个子问题如何求解？划分思想的本质就是缩减问题规模使之可以在多项式时间内求解,但有的问题即使缩减了规模仍然很难求解，如加权问题.为子问题设计近似算法是一种解决方式.②如何将子问题的解拼接成原问题的解？如Cheng等人在文献[16]中通过边界区域与内部区域一定程度的重迭保证了最终解的整体连通性.然而，如何去获得更高阶的整体连通性仍然是有待探索的问题.③分析中如何使最优解与计算解之间具有可比性？一个自然的想法是把最优解限制在子问题上，经过一定的改造使之成为子问题的可行解,它依赖于如何合理定义子问题的可行解.划分平移的方法被广泛应用于具有一定几何特性的问题中，如可平图、几何交图等.划分方法还有很多有趣的变形，如多重网格划分方法[67]、Guillotine割法[12]等，它们更适合于设计不规则问题的自适应算法.

3) 局域搜索算法

局域搜索算法也是一个经典的组合方法，它的思想是用局域最优解来近似整体最优解.Mustafa等人[64]将它成功地应用于几何覆盖问题上，其桥梁是可平图的分离元定理.该定理也是分而治之思想的体现，但在解决虚拟骨干问题时，它只用于近似比的分析而不是算法的实现.对于各种具有几何结构的问题，是否存在类似的分离元定理是这类问题分析的关键，它与计算几何学密切相关.

除了上述方法之外，在研究虚拟骨干近似算法的过程中，还需要综合应用多种工具.如虚拟骨干的连通部分本质上是个Steiner问题，Steiner领域的任何进展都有助于该问题的推进.目前Steiner问题最好的近似比大多基于线性规划和随机算法.又如容错虚拟骨干的组合算法，目前主要使用连通度逐次提升的思想，它强烈依赖于高阶连通图的递归结构，与图论领域的研究密切相关.由于无线传感器网络的几何特性，几何学更是广泛地应用于虚拟骨干近似算法的分析之中.例如目前很多算法的分析都基于圆盘图中的独立点集比较稀疏这一几何性质.

2.2研究展望

在无线传感网虚拟骨干近似算法的研究中，以下4个问题是长期悬而未决的，它们的解决需要更深的洞察力和理论上的创新.

1) 在不对传输半径作任何假设的条件下，圆盘图中最小强连通控制吸收集问题是否存在常数近似算法？我们已经可以得到最小控制吸收集的(2+ε)-近似.该问题的难点在于强连通部分.可以证明，对于一个控制吸收集来说，距离最近的2个强连通分支之间3步可达,然而，方向性带来本质困难.可以构造出圆盘图G和控制吸收集C，加入2个点即可使C单向连通，但要使得C强连通，需要加入非常非常多的点.一个或许可行的思路是证明如果出现上述情况，则最优解中一定也含有很多点.

2) 高维空间无向球图(半径可以不同)最小控制集问题是否存在PTAS近似算法？在平面上，该问题用局域搜索的方法可以得到PTAS.该方法成功的关键有2个:①可平图的分离元定理;②满足局域条件(locality condition)的可平图的存在性.我们在文献[68]中得到了d维空间无向球图的分离元定理.然而，满足局域条件的可平图是否存在还是尚待回答的问题.

3) 一般图中最小权连通控制集问题是否有比(1.35+ε)lnn更好的近似比？该近似比自1999年得到以来[40]，16年没有任何改进.该算法运用了贪婪策略.很多与图相关的贪婪算法，其近似比都具有O(lnΔ)的形式，其中Δ是图的最大度.故上述近似比中的参数n能否改进到Δ，这是一个很有趣的问题.

4) 单位圆盘图中是否存在关系

α≤3γc+3

(5)

事实上Vahdatpour等人[69]声称他们证明了这一关系,然而其证明并不严密(参见文献[70]中的说明).Wan等人在文献[23]中构造了一个实例G，对该实例来说α(G)≥3γc(G)+3.故如果式(5)成立，则它将是紧的.

虽然本文对于以上问题提供了作者的一些初步思考，但它们的解决或许需要全新的思路，希望能引起读者的兴趣，集思广益，在其解决过程中创造出新的方法和新的工具.

有学者还研究了具有最小直径的虚拟骨干问题[71]、负载均衡的虚拟骨干问题[72-73]等.考虑虚拟骨干的多目标优化问题是一个非常有趣的研究课题.在动态环境下研究虚拟骨干的维护算法是一个尚未充分展开的研究内容[74].充分挖掘最小连通控制集问题的结论、理论、与方法在相关研究中的应用也是研究者关注的一个重点.

参考文献

[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)(刘清海. 几类组合优化问题的算法研究[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)(秦云龙, 禹继国, 王康. 无线移动网络中k连通m控制集的一个维护算法[J]. 计算机技术与发展, 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)；新疆杰出青年科技人才培养项目(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).