三維無線傳感器網絡的中繼器放置問題

崔素輝，陳光亭，李茹雪

（杭州電子科技大學理學院運籌與控制研究所，浙江杭州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.