崔素輝，陳光亭，李茹雪

（杭州電子科技大學(xué)理學(xué)院運籌與控制研究所，浙江杭州310018）

0 引 言

無線傳感器網(wǎng)絡(luò)的研究大多是基于二維平面的，最近，地下水深測量三維無線傳感網(wǎng)絡(luò)已經(jīng)引起了許多研究者的興趣，海洋監(jiān)控網(wǎng)絡(luò)中對于不同深度的監(jiān)測，以及天氣預(yù)報及氣候監(jiān)測也使得三維空間中無線傳感網(wǎng)絡(luò)的研究變得更加有意義。文獻1對三維空間地下水深測量進行了研究，文獻2、3對于三維空間中的感應(yīng)覆蓋問題進行了討論，文獻4針對三維空間中的路由問題進行研究，文獻5針對三維空間中的定位問題設(shè)計算法，而本文首先對三維空間中雙層網(wǎng)絡(luò)上中繼器放置問題進行了討論，在一定的條件下，給出了常數(shù)性能比近似算法。

1 雙層網(wǎng)絡(luò)問題模型

在無線傳感器網(wǎng)絡(luò)中，如果傳感器在其傳輸半徑范圍內(nèi)只能將信息傳輸?shù)礁吣艿闹欣^器，而中繼器可以在傳輸半徑范圍內(nèi)將信息傳輸?shù)街欣^器，則稱這樣的網(wǎng)絡(luò)為雙層無線傳感器網(wǎng)絡(luò)。

在三維空間中，設(shè)傳感器的集合為X=｛x1，x2，x3，…xn｝，Y表示放置的高能中繼器集合，其中xi的傳輸半徑均為r，高能中繼器傳輸半徑均為R，并假設(shè)R≥4r。用d表示兩點之間距離，構(gòu)造無向圖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）。

雙層網(wǎng)絡(luò)單覆蓋單連通問題要求在無線傳感器網(wǎng)絡(luò)中放置最少數(shù)目的中繼器，使得在無向圖G=（V，E）中，滿足：

（1）每個傳感器點至少可以跟一個中繼器點有邊相連，即每個傳感器被中繼器覆蓋；

（2）任意兩個中繼器點之間至少存在一條由中繼器點構(gòu)成的路，即中繼器網(wǎng)絡(luò)達到連通。

而雙層網(wǎng)絡(luò)雙覆蓋雙連通問題則要求在無線傳感器網(wǎng)絡(luò)中放入最小數(shù)目的中繼器，使得在無向圖G=（V，E）中，滿足：

（1）每個傳感器至少可以跟兩個中繼器點有邊相連；

（2）任意兩個中繼器點之間至少存在兩條由中繼器點構(gòu)成的不相交的路。

2 算法分析與設(shè)計

定義在三維空間中，把點p叫做放置中繼器的P-position，如果存在兩個傳感點s，s′，使得d（s，p）=d（s′，p）=r。

在每個正方體細胞中最初的放置中繼器規(guī)則為：用C表示最初放置的中繼器集合，起初令C=?，對于細胞內(nèi)的任意兩個傳感器點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。

在將長方體劃分為細胞時，根據(jù)文獻6的思想，將其劃分為邊長為2rw的正方體細胞，其中w為正整數(shù)，稱其為算法因子，這里以w=1，w=2為例來設(shè)計算法。需要說明的是，在給出下面每一個算法之前，都必須先做如下處理：用最小的長方體把整個區(qū)域包圍，然后將此長方體劃分為邊長為2rw的小正方體細胞。除去不包含傳感器點的細胞，對于其它細胞，運用最初的放置中繼器規(guī)則找出覆蓋每個細胞的中繼器集合C。

算法1 雙層網(wǎng)絡(luò)單覆蓋單連通問題（w=1）

步驟1 對于每個細胞，搜索C中元素數(shù)目為1-8的子集，找到最少數(shù)目的中繼器點來覆蓋該細胞上所有的傳感器點。

步驟2 對于每個細胞Bi，令Hi為步驟1找到的覆蓋Bi中傳感器的中繼器集合。設(shè)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在區(qū)域的邊界上，則在細胞Bi的某個在區(qū)域內(nèi)部的頂點處放入一個中繼器。

圖1 細胞Bi

算法2 雙層網(wǎng)絡(luò)單覆蓋單連通問題（w=2）

步驟1 在每個細胞上，搜索C中元素數(shù)目為1-64的子集，找到最少數(shù)目的點覆蓋該細胞內(nèi)所有的傳感器點。

步驟2 使中繼器網(wǎng)絡(luò)達到連通。

（1）使細胞內(nèi)的中繼器連通。對于每個細胞Bi，令Hi為步驟1找到的覆蓋Bi中傳感器的中繼器集合，如果細胞內(nèi)的中繼器沒有連通，在細胞的中心位置放入一中繼器q，且令Hi=Hi∪｛q｝。

（2）使不同細胞內(nèi)的中繼器連通。設(shè)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ǎng)絡(luò)雙覆蓋雙連通問題（w=1）

步驟1 在每個細胞上，搜索C中元素數(shù)目為1-16的子集，找到最少數(shù)目的點雙覆蓋該細胞內(nèi)所有的傳感器點。

步驟2 使得距離較近的中繼器點達到雙連通。

（1）使得每一x行的中繼器連通。

令Hi為步驟1找到的覆蓋Bi中傳感器的中繼器集合。設(shè)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｝。重復(fù)此過程，使得每一行中繼器均達到連通。

（2）使得每一y列中繼器連通。

（3）使得每一z列中繼器連通。

如果 H′i+z與 H′i不連通，同樣在 G 點處放入一中繼器 q′，且令 Hi+1=Hi+1∪｛q′｝。

算法4 雙層網(wǎng)絡(luò)雙覆蓋雙連通問題（w=2）

步驟1 在每個細胞上，搜索C中元素數(shù)目為1-128的子集，找到最少數(shù)目的點雙覆蓋該細胞內(nèi)所有的傳感點。對于每個細胞Bi，用Hi表示雙覆蓋Bi中傳感器點的中繼器集合。

步驟2 在每個細胞Bi中，如果Hi的中繼器能夠達到連通但沒有達到雙連通，就在此細胞的DF上距A、B距離均為4r處的J、K處放入兩個中繼器，如圖1所示。

步驟3 使得距離較近的中繼器達到雙連通。

（1）使得每一x行的中繼器連通。

設(shè) 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引理 給定三維空間區(qū)域上的點集，為了覆蓋區(qū)域所有的點，用A表示區(qū)域劃分后用于任意邊長為2rw的小正方體內(nèi)的近似算法，SA為表示用于整個長方體內(nèi)的近似算法，即在每個小正方體運用算法A得到的并［6］。令rA為算法A的性能比，rSA為算法SA的性能比，則有

證明 首先算法3保證了每個傳感器至少被兩個中繼器覆蓋，其次算法3也保證了放置的中繼器網(wǎng)絡(luò)達到了雙連通。很顯然每個細胞內(nèi)的中繼器一定是雙連通的，并且任意不在同一個細胞內(nèi)的中繼器點q與q′也能夠達到雙連通。

令H′表示步驟2產(chǎn)生的中繼器的集合，即H′=∪Hi，根據(jù)Shifting引理，則有）3=8。令H*表示算法3得到的中繼器集合，則H′在每個細胞中至少包含兩個中繼器，然而算法3在每個細胞中又最多加入了1個中繼器點，于是有，則有

4 結(jié) 論

本文在w=1，2時分別設(shè)計了相應(yīng)的算法，當(dāng)w=2時的性能比更好，但是隨著w的增大，時間復(fù)雜性也會增大。本文運用區(qū)域劃分的思想，將三維空間上的覆蓋與連通問題轉(zhuǎn)移到了范圍較小的細胞上研究，根據(jù)細胞與球的半徑關(guān)系，解決了三維空間上的覆蓋與連通的問題，拓寬了無線傳感器網(wǎng)絡(luò)在三維空間中的應(yīng)用領(lǐng)域。

［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.