单层网络中继器放置的2-连通问题及算法

(杭州电子科技大学理学院，浙江 杭州310018)

0 引 言

无线传感器网络是由基站和大量价格低廉、能量较少的传感器组成的。在无线传感器网络中，传感器主要作用是感知周围的环境，并把收集到的信息传送给基站。传感器节点在恶劣的环境中随机的分布，能量只能由不能随意更换的电池提供。但是能量消耗在长距离通讯中却以距离指数的形式快速增加，所以研究者们提出了在无线传感网络中放置一定数目的中继器的思路，这成为了减少能量损耗的重要方法。对单层网络的2-连通问题，文献1 设计了R=r 且不含基站情形的近似算法，并证明其性能比为10。当R≥r时，文献2 对不含基站和含有基站两种情形分别设计了性能比为14和16的近似算法。本文研究含有基站的单层网络2-连通问题，对R=r的情形设计了性能比为12的近似算法。

1 单层网络2-连通问题的基本概念

B表示已知的基站集合，X表示已知的传感器集合，Y表示放置的中继器集合，并用d (x，y)表示平面上的点x和y的距离。假设传感器的传输半径为r，中继器的传输半径为R≥r。在单层无线传感器网络中，传感器在传输半径内可以和中继器、基站、其他传感器传输数据，中继器在传输半径内可以和基站、其他中继器传输数据，这里都是假设基站的传输半径足够大，基站之间可以直接通讯。对给定的(R，r，B，X，Y)，构造单层网络上的混合无向连通图HCG (R，r，B，X，Y)，其中顶点集为V=B∪X∪Y，边集E 定义为:

(1)对任意两个基站顶点bi，bj∈B，E 都包含无向边(bi，bj)=(bj，bi);

(2)对任意中继器顶点y∈Y以及顶点z∈Y∪B，如果d(y，z)≤R，则E 包含无向边(y，z)=(z，y);

(3)对任意传感器顶点x∈X以及顶点z∈X∪Y∪B，如果d(x，z)≤r，则E 包含无向边(x，z)=(z，x)。

单层无线传感器网络的2-连通问题，就是要求放置最少数目的中继器集合Y，使得图HCG (R，r，B，X，Y)网络中的任意两个顶点之间至少存在两条不相交的路，即保证该图HCG (R，r，B，X，Y)是2-连通的。

当R=r时，文献1 证明了问题在不含基站的情形下已经是NP-hard的，因此含有基站的情形也必是NP-hard的。

2 近似算法设计

首先，构造由顶点集B∪X 导出的无向完全图GC。对GC中任意两顶点zi和zj(不全是基站顶点)，若它们的距离d(zi，zj)≤r，则它们在图HCG 中直接相连。若d(zi，zj)＞r，则可以采取边斯坦纳化方法使之连通[3]。即在边(zi，zj)上按照以下方式放置中继器:

(1)如果r ＜d(zi，zj)≤2r，则在(zi，zj)的中间位置放入一个中继器点;

(2)如果d(zi，zj)＞2r，则在(zi，zj)上放入两个中继器点yF，yL，使得d(zi，yF)=r，d(zj，yL)=r，再在边(yF，yL)上均匀放置个中继器。

边(zi，zj)的权重c(zi，zj)如下易知c(zi，zj)恰是对边(zi，zj)斯坦纳化应放置的中继器数目，接下来给出2-连通问题的具体算法。

算法1 单层网络2-连通问题。

输入 传感器集合X= {x1，x2，…，xn}，基站集合B= {b1，b2，…，bn}及常数R=r。

输出 中继器集合Y。

步骤1 由B∪X 构建无向完全图GC。

步骤2 对GC中的每条边(zi，zj)赋权重c(zi，zj)。

步骤3 利用文献4中的算法得到GC的一个2-连通生成子图G'C。

步骤4 在G'C的每条边上按边斯坦纳化方法放置中继器，并把这些顶点加到集合Y中，构建图HCG (R，r，B，X，Y)。

3 算法性能比分析

在传感器顶点和基站顶点之间放置的中继器称为珠子，最优解放置的中继器称为斯坦纳点，S表示全部的斯坦纳点个数。主要结论是下述定理:

定理1算法1 得到的2-连通网络最多需要放置12S 珠子，即性能比为12。

为证明定理，接下来先给出几个重要的引理。

引理1 在2-连通的中继器放置无线传感器网络中，与任意一个中继器相连的传感器个数不超过5[5]，与任意一个中继器相连的基站个数不超过1[2]。

引理2 终点集B∪X 导出的赋权完全图GC的最小2-连通子图的权重不超过6S，即由此产生的2-连通网络中至多有6S个珠子。

证明 令G0=(V0，E0)为放置最少数目中继器构成的最优2-连通网络，即其中的中继器均为斯坦纳点。接下来构建只含有珠子而不含有斯坦纳点的2-连通网络Gm(m≥1)，证明网络中最多含有6S个珠子。

从j=1 开始，由Gj-1构造Gj，具体过程如下:

第一步 找出G0中由斯坦纳点构成的连通分支SCi(1≤i≤m)，然后对于每个连通分支找出度数之和最小的支撑树ST1，ST2，…，STm，如图1所示;

第二步 用Hj表示STj与其传输范围内的终点集Vj构成的树，如图2所示;

第三步 找出Hj中边数最多的路径，以该路的一端点t1(必为叶子顶点)为树的根，计算树上其余顶点到根之间的边数，定义为该顶点的深度。按照深度优先搜索法，从t1开始遍历Hj的所有叶子顶点，即终点集。按遍历先后顺序连接所有的终点，得到一个终点集构成的圈，如图3所示;

第四步 去掉Hj中的斯坦纳点，并终点集构成的圈的每条边上按照边斯坦纳化方法放置中继器(珠子)。从而，包含珠子的圈上任意两点之间均存在2条不相交的路，如图4所示。

图1 最小的支撑树STj

图2 斯坦纳点与终点构成的树Hj

图3 终点集Vj 构成的圈

图4 去掉斯坦纳点

从Gj-1构造Gj，就是从Gj-1去掉STj中斯坦纳点集及其相连接的边集，然后把由Vj生成的圈放入Gj-1，便得到Gj。因此，最后可以得到只含有珠子而不含有斯坦纳点的2-连通网络Gm。

用bj表示从Gj-1构造Gj过程中增加的珠子个数，Sj表示STj中的斯坦纳点个数，b表示构造网络Gm整个过程所需要增加的珠子总数。注意到树STj中经过同一个斯坦纳点的两条边的夹角均不小于60°[6]，所以任意两个终点相连所需放置的珠子个数不会超过遍历搜索的斯坦纳点个数，如图5所示，图5(a)、(b)、(c)分别表示1个斯坦纳点、2个斯坦纳点及n个斯坦纳点的情形。结合根据引理1，可知终点个数最多为6Sj，即bj≤5Sj+Sj=6Sj，于是总的放入的珠子数目为引理2 得证。

图5 两个终点相连的情况

接下来给出定理1的证明。

证明 注意到算法1 在第3步中利用了文献4的算法去寻找最小2-连通生成子图，由于该算法的性能比不超过2[4]，而按照引理2，放置珠子的数目为斯坦纳点的6倍，于是算法1 需要加入的珠子至多为斯坦纳点的2×6 =12倍，定理1 得证。

4 结束语

本文主要研究了含有基站的单层网络的中继器放置问题。对单层无线传感器网络2-连通问题，设计了R=r 情形的近似算法，性能比为12，这是一个新结果。

[1]Kashyap A，Khuller S，Shayman M.Relay placement for higher order connectivity in wireless sensor networks[C].Barcelona:IEEE International Conference on Computer Communications，2006:1-12.

[2]Zhang W，Xue G，Misra S.Fault-Tolerant Relay Node Placement in Wireless Sensor Networks:Problems and Algorithms[C].Anchorage∶IEEE International Conference on Computer Communications，2007:1 649-1 659.

[3]Lin G，Xue G.Steiner tree problem with minimum number of Steiner point and bounded edge-length[J].Information Processing Letters，1999，69(2):53-57.

[4]Khuller S，Raghavachari B.Improved approximation algorithms for uniform connectivity problems[C].New York:the twenty-seventh annual ACM symposium on Theory of computing，1995∶214-235.

[5]Monma C，Suri S.Transitions in geometric minimum spanning tree[J].Discrete and Computational Geometry，1992，8(1):265-293.

[6]Chen D，Wang L，Xue G.Approximations for steiner trees with minimum number of steiner points[J].Journal of Global Optimization，2000，18(1):17-33.