崔素辉，陈光亭，李茹雪

（杭州电子科技大学理学院运筹与控制研究所，浙江杭州310018）

0 引 言

无线传感器网络的研究大多是基于二维平面的，最近，地下水深测量三维无线传感网络已经引起了许多研究者的兴趣，海洋监控网络中对于不同深度的监测，以及天气预报及气候监测也使得三维空间中无线传感网络的研究变得更加有意义。文献1对三维空间地下水深测量进行了研究，文献2、3对于三维空间中的感应覆盖问题进行了讨论，文献4针对三维空间中的路由问题进行研究，文献5针对三维空间中的定位问题设计算法，而本文首先对三维空间中双层网络上中继器放置问题进行了讨论，在一定的条件下，给出了常数性能比近似算法。

1 双层网络问题模型

在无线传感器网络中，如果传感器在其传输半径范围内只能将信息传输到高能的中继器，而中继器可以在传输半径范围内将信息传输到中继器，则称这样的网络为双层无线传感器网络。

在三维空间中，设传感器的集合为X=｛x1，x2，x3，…xn｝，Y表示放置的高能中继器集合，其中xi的传输半径均为r，高能中继器传输半径均为R，并假设R≥4r。用d表示两点之间距离，构造无向图G=（V，E），其中点集V=X∪Y，边集E定义为：

（1）对于任意点x∈X，y∈Y，如果d（x，y）≤r，则E包含边（x，y）；

（2）对于任意点，z∈Y，e∈Y，如果d（z，e）≤R，则E包含边（z，e）。

双层网络单覆盖单连通问题要求在无线传感器网络中放置最少数目的中继器，使得在无向图G=（V，E）中，满足：

（1）每个传感器点至少可以跟一个中继器点有边相连，即每个传感器被中继器覆盖；

（2）任意两个中继器点之间至少存在一条由中继器点构成的路，即中继器网络达到连通。

而双层网络双覆盖双连通问题则要求在无线传感器网络中放入最小数目的中继器，使得在无向图G=（V，E）中，满足：

（1）每个传感器至少可以跟两个中继器点有边相连；

（2）任意两个中继器点之间至少存在两条由中继器点构成的不相交的路。

2 算法分析与设计

定义在三维空间中，把点p叫做放置中继器的P-position，如果存在两个传感点s，s′，使得d（s，p）=d（s′，p）=r。

在每个正方体细胞中最初的放置中继器规则为：用C表示最初放置的中继器集合，起初令C=Ø，对于细胞内的任意两个传感器点s，s′，如果d（s，s′）＜2r，一定存在一圆，使得圆上每一点p，都满足d（s，p）

=d（s′，p）=r。圆上每一点都可以作为放置中继器的P-position，从圆上任意选择两点放入C，如果d（s，s′）=2r，则只存在一点为其P-position，选择此点放入C；如果d（s，s′）＞2r，这样P-position的点是不存在的，于是分别在两个球上各找一点放入C，如此进行下去，可以找到覆盖细胞的中继器集合C。

在将长方体划分为细胞时，根据文献6的思想，将其划分为边长为2rw的正方体细胞，其中w为正整数，称其为算法因子，这里以w=1，w=2为例来设计算法。需要说明的是，在给出下面每一个算法之前，都必须先做如下处理：用最小的长方体把整个区域包围，然后将此长方体划分为边长为2rw的小正方体细胞。除去不包含传感器点的细胞，对于其它细胞，运用最初的放置中继器规则找出覆盖每个细胞的中继器集合C。

算法1 双层网络单覆盖单连通问题（w=1）

步骤1 对于每个细胞，搜索C中元素数目为1-8的子集，找到最少数目的中继器点来覆盖该细胞上所有的传感器点。

步骤2 对于每个细胞Bi，令Hi为步骤1找到的覆盖Bi中传感器的中继器集合。设Bi+x为Bi右面的相邻细胞，Bi+y为 Bi下面的相邻细胞，Bi+z为 Bi前面的相邻细胞，则 Bi+x、Bi+y与 Bi+z分别为覆盖Bi+x、Bi+y与Bi+z中传感器的中继器集合，如果Hi与Bi+x或Bi+y或Bi+z不连通，就在细胞Bi的G点处放置一个中继器，如图1所示。如果细胞Bi在区域的边界上，则在细胞Bi的某个在区域内部的顶点处放入一个中继器。

图1 细胞Bi

算法2 双层网络单覆盖单连通问题（w=2）

步骤1 在每个细胞上，搜索C中元素数目为1-64的子集，找到最少数目的点覆盖该细胞内所有的传感器点。

步骤2 使中继器网络达到连通。

（1）使细胞内的中继器连通。对于每个细胞Bi，令Hi为步骤1找到的覆盖Bi中传感器的中继器集合，如果细胞内的中继器没有连通，在细胞的中心位置放入一中继器q，且令Hi=Hi∪｛q｝。

（2）使不同细胞内的中继器连通。设Bi+x为Bi右面的相邻细胞，Bi+y为Bi下面的相邻细胞，Bi+z为Bi前面的相邻细胞，则Bi+x、Bi+y与Bi+z分别为覆盖Bi+x、Bi+y与Bi+z中传感器的中继器集合，如果Hi与Hi+x不连通，就在Hi的中心位置放入中继点qi，如果还没有达到连通，在Hi+x的中心位置放入qi+x。

算法3 双层网络双覆盖双连通问题（w=1）

步骤1 在每个细胞上，搜索C中元素数目为1-16的子集，找到最少数目的点双覆盖该细胞内所有的传感器点。

步骤2 使得距离较近的中继器点达到双连通。

（1）使得每一x行的中继器连通。

令Hi为步骤1找到的覆盖Bi中传感器的中继器集合。设Bi+x为Bi右面的相邻细胞，Bi+y为Bi下面的相邻细胞，Bi+z为Bi前面的相邻细胞，则Hi+x、Hi+y与 Hi+z分别为覆盖 Bi+x、Bi+y与 Bi+z中传感器的中继器集合，如果Hi与Hi+x不连通，就在Bi的G点处放入一个中继器qi，如图1所示，且令Hi=Hi∪｛qi｝。重复此过程，使得每一行中继器均达到连通。

（2）使得每一y列中继器连通。

（3）使得每一z列中继器连通。

如果 H′i+z与 H′i不连通，同样在 G 点处放入一中继器 q′，且令 Hi+1=Hi+1∪｛q′｝。

算法4 双层网络双覆盖双连通问题（w=2）

步骤1 在每个细胞上，搜索C中元素数目为1-128的子集，找到最少数目的点双覆盖该细胞内所有的传感点。对于每个细胞Bi，用Hi表示双覆盖Bi中传感器点的中继器集合。

步骤2 在每个细胞Bi中，如果Hi的中继器能够达到连通但没有达到双连通，就在此细胞的DF上距A、B距离均为4r处的J、K处放入两个中继器，如图1所示。

步骤3 使得距离较近的中继器达到双连通。

（1）使得每一x行的中继器连通。

设 Bi+x为 Bi右面的相邻细胞，Bi+y为 Bi下面的相邻细胞，Bi+z为 Bi前面的相邻细胞，则 Hi+x、Hi+y与Hi+z分别为覆盖Bi+x、Bi+y与Bi+z中传感器的中继器集合，如果Hi与Hi+x不连通，就在Bi的J点处放入一个中继器qi，且令Hi=Hi∪｛qi｝，如果还是不能够达到连通，就在Bi+1的J点处再加入一个中继器qi+1，且令 Hi+1=Hi+1∪｛qi+1｝。

（2）使得每一y列中继器连通。

（3）使得每一z列中继器连通。

3 算法性能比分析

Shifting引理 给定三维空间区域上的点集，为了覆盖区域所有的点，用A表示区域划分后用于任意边长为2rw的小正方体内的近似算法，SA为表示用于整个长方体内的近似算法，即在每个小正方体运用算法A得到的并［6］。令rA为算法A的性能比，rSA为算法SA的性能比，则有

证明 首先算法3保证了每个传感器至少被两个中继器覆盖，其次算法3也保证了放置的中继器网络达到了双连通。很显然每个细胞内的中继器一定是双连通的，并且任意不在同一个细胞内的中继器点q与q′也能够达到双连通。

令H′表示步骤2产生的中继器的集合，即H′=∪Hi，根据Shifting引理，则有）3=8。令H*表示算法3得到的中继器集合，则H′在每个细胞中至少包含两个中继器，然而算法3在每个细胞中又最多加入了1个中继器点，于是有，则有

4 结 论

本文在w=1，2时分别设计了相应的算法，当w=2时的性能比更好，但是随着w的增大，时间复杂性也会增大。本文运用区域划分的思想，将三维空间上的覆盖与连通问题转移到了范围较小的细胞上研究，根据细胞与球的半径关系，解决了三维空间上的覆盖与连通的问题，拓宽了无线传感器网络在三维空间中的应用领域。

［1］ Akyildiz IF，Pompili D，Melodia T.Underwater Acoustic Sensor Networks：Research Challenges［J］.Ad Hoc Networks，2005，3（3）：257-279.

［2］ Huang Chifu，Tseng Yuchee，Lo Lichu.The Coverage Problem in Three-Dimensional Wireless Sensor Networks［J］.Global Telecomm-unications Conference，2004，4（5）：182-186.

［3］ Alam SN，Haas Z.Coverage and connectivity in three dimensional networks［J］.International Conference on Mobile Computing and Networking，2006，6（5）：346-357.

［4］ Tarek El Salti，Nidal Nasser.Routing in Three Dimensional Wireless Sensor Networks［J］.Global Telecomm-unications Conference，2008，5（30）：1-6.

［5］ Li Kai，Zheng Shijue，Zheng Zhenhua，et al.Research on Three-Dimensional Localization Algorithm in Wireless Sensor Network［J］.Antennas and Propagation Society International Symposium，2008，8（16）：500-503.

［6］ Hochbaum D S，Maass W.Approximation schemes for covering and packing problems in image processing and VLSI［J］.Journal of ACM，1985，5（32）：130-136.

［7］ Tang J，Hao B，Sen A.Relay node placement in large scale wireless sensor networks［J］.Computer Communications，2006，7（29）：490-501.