崔素輝，陳光亭，李茹雪

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

0 引 言

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

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

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

在三維空間中，設(shè)傳感器的集合為X=｛x1，x2，x3，…xn｝，Y表示放置的高能中繼器集合，其中xi的傳輸半徑均為r，高能中繼器傳輸半徑均為R，并假設(shè)R≥4r。用d表示兩點(diǎn)之間距離，構(gòu)造無(wú)向圖G=（V，E），其中點(diǎn)集V=X∪Y，邊集E定義為：

（1）對(duì)于任意點(diǎn)x∈X，y∈Y，如果d（x，y）≤r，則E包含邊（x，y）；

（2）對(duì)于任意點(diǎn)，z∈Y，e∈Y，如果d（z，e）≤R，則E包含邊（z，e）。

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

（1）每個(gè)傳感器點(diǎn)至少可以跟一個(gè)中繼器點(diǎn)有邊相連，即每個(gè)傳感器被中繼器覆蓋；

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

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

（1）每個(gè)傳感器至少可以跟兩個(gè)中繼器點(diǎn)有邊相連；

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

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

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

在每個(gè)正方體細(xì)胞中最初的放置中繼器規(guī)則為：用C表示最初放置的中繼器集合，起初令C=?，對(duì)于細(xì)胞內(nèi)的任意兩個(gè)傳感器點(diǎn)s，s′，如果d（s，s′）＜2r，一定存在一圓，使得圓上每一點(diǎn)p，都滿足d（s，p）

=d（s′，p）=r。圓上每一點(diǎn)都可以作為放置中繼器的P-position，從圓上任意選擇兩點(diǎn)放入C，如果d（s，s′）=2r，則只存在一點(diǎn)為其P-position，選擇此點(diǎn)放入C；如果d（s，s′）＞2r，這樣P-position的點(diǎn)是不存在的，于是分別在兩個(gè)球上各找一點(diǎn)放入C，如此進(jìn)行下去，可以找到覆蓋細(xì)胞的中繼器集合C。

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

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

步驟1 對(duì)于每個(gè)細(xì)胞，搜索C中元素?cái)?shù)目為1-8的子集，找到最少數(shù)目的中繼器點(diǎn)來(lái)覆蓋該細(xì)胞上所有的傳感器點(diǎn)。

步驟2 對(duì)于每個(gè)細(xì)胞Bi，令Hi為步驟1找到的覆蓋Bi中傳感器的中繼器集合。設(shè)Bi+x為Bi右面的相鄰細(xì)胞，Bi+y為 Bi下面的相鄰細(xì)胞，Bi+z為 Bi前面的相鄰細(xì)胞，則 Bi+x、Bi+y與 Bi+z分別為覆蓋Bi+x、Bi+y與Bi+z中傳感器的中繼器集合，如果Hi與Bi+x或Bi+y或Bi+z不連通，就在細(xì)胞Bi的G點(diǎn)處放置一個(gè)中繼器，如圖1所示。如果細(xì)胞Bi在區(qū)域的邊界上，則在細(xì)胞Bi的某個(gè)在區(qū)域內(nèi)部的頂點(diǎn)處放入一個(gè)中繼器。

圖1 細(xì)胞Bi

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

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

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

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

（2）使不同細(xì)胞內(nèi)的中繼器連通。設(shè)Bi+x為Bi右面的相鄰細(xì)胞，Bi+y為Bi下面的相鄰細(xì)胞，Bi+z為Bi前面的相鄰細(xì)胞，則Bi+x、Bi+y與Bi+z分別為覆蓋Bi+x、Bi+y與Bi+z中傳感器的中繼器集合，如果Hi與Hi+x不連通，就在Hi的中心位置放入中繼點(diǎn)qi，如果還沒(méi)有達(dá)到連通，在Hi+x的中心位置放入qi+x。

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

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

步驟2 使得距離較近的中繼器點(diǎn)達(dá)到雙連通。

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

令Hi為步驟1找到的覆蓋Bi中傳感器的中繼器集合。設(shè)Bi+x為Bi右面的相鄰細(xì)胞，Bi+y為Bi下面的相鄰細(xì)胞，Bi+z為Bi前面的相鄰細(xì)胞，則Hi+x、Hi+y與 Hi+z分別為覆蓋 Bi+x、Bi+y與 Bi+z中傳感器的中繼器集合，如果Hi與Hi+x不連通，就在Bi的G點(diǎn)處放入一個(gè)中繼器qi，如圖1所示，且令Hi=Hi∪｛qi｝。重復(fù)此過(guò)程，使得每一行中繼器均達(dá)到連通。

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

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

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

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

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

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

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

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

設(shè) Bi+x為 Bi右面的相鄰細(xì)胞，Bi+y為 Bi下面的相鄰細(xì)胞，Bi+z為 Bi前面的相鄰細(xì)胞，則 Hi+x、Hi+y與Hi+z分別為覆蓋Bi+x、Bi+y與Bi+z中傳感器的中繼器集合，如果Hi與Hi+x不連通，就在Bi的J點(diǎn)處放入一個(gè)中繼器qi，且令Hi=Hi∪｛qi｝，如果還是不能夠達(dá)到連通，就在Bi+1的J點(diǎn)處再加入一個(gè)中繼器qi+1，且令 Hi+1=Hi+1∪｛qi+1｝。

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

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

3 算法性能比分析

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

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

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

4 結(jié) 論

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