(杭州電子科技大學(xué)理學(xué)院，浙江 杭州310018)

0 引 言

在無(wú)線傳感網(wǎng)絡(luò)中，如果傳感器在傳輸半徑范圍內(nèi)只能將信息傳遞給高能的中繼器，而中繼器與中繼器之間在傳輸半徑范圍內(nèi)可以相互傳遞信息，這樣的網(wǎng)絡(luò)稱為雙層無(wú)線傳感網(wǎng)絡(luò)。文獻(xiàn)1 首先對(duì)無(wú)線傳感網(wǎng)絡(luò)2-覆蓋2-連通進(jìn)行了研究，在R≥2r的條件下，給出了性能比為O(Dlogn)的貪婪算法，其中D為網(wǎng)絡(luò)的直徑，n為傳感器的數(shù)目。文獻(xiàn)2 假設(shè)傳感器集分布在矩形區(qū)域內(nèi)，在R≥4r的條件下給出了兩個(gè)單覆蓋單連通的算法性能比分別為8和6，兩個(gè)雙覆蓋雙連通的算法，性能比均為9/，而文獻(xiàn)3則在三維空間中對(duì)該問(wèn)題進(jìn)行了討論。文獻(xiàn)4 在R=r的假設(shè)前提下針對(duì)2-覆蓋2-連通問(wèn)題設(shè)計(jì)了性能比為24+ε和6/T+12+ε的兩種近似算法，其中T為單覆蓋單連通問(wèn)題中放置的中繼器數(shù)目與網(wǎng)絡(luò)中傳感器數(shù)目的比值。本文在雙層無(wú)線傳感網(wǎng)絡(luò)中加入基站，且在R≥4r的情況下，針對(duì)k-覆蓋k-連通問(wèn)題設(shè)計(jì)了性能比為9/2的近似算法，并給出性能比分析。

1 問(wèn)題描述與定義

在雙層無(wú)線傳感網(wǎng)絡(luò)中，中繼器可以在傳輸半徑范圍內(nèi)與基站和其他中繼器相互傳遞信息，基站與基站可以直接傳遞信息。設(shè)傳感器的集合為X，基站的集合為B，Y表示放置的高能中繼器集合，基站的通訊能力是無(wú)窮的。

這里假設(shè)R≥4r，對(duì)給定的(r，R，B，X，Y)，設(shè)中繼器的傳輸半徑為R，傳感器的傳輸半徑為r，給出雙層無(wú)線傳感網(wǎng)絡(luò)上的混合通訊圖MTC(r，R，B，X，Y)的構(gòu)造方法，其中頂點(diǎn)集V =BUXUY，邊集E 定義如下:

(1)對(duì)任意頂點(diǎn)bi，bj∈B，E 包含無(wú)向邊(bi，bj);

(2)對(duì)任意頂點(diǎn)y∈Y，z∈Y∪B，如果d (y，z)≤R，則E 包含無(wú)向邊(y，z);

(3)對(duì)任意頂點(diǎn)x∈X，z∈Y∪B，如果d (x，z)≤R，則E 包含無(wú)向邊(x，z)。

本文研究雙層無(wú)線傳感網(wǎng)絡(luò)的k-覆蓋k-連通放置問(wèn)題，即放置最小數(shù)目的中繼器，使得在MTC(r，R，B，X，Y)網(wǎng)絡(luò)中滿足以下兩個(gè)條件:

(1)每個(gè)傳感器至少被k個(gè)中繼器覆蓋，即每個(gè)傳感器至少與k個(gè)中繼器相連;

(2)中繼器與基站構(gòu)成的網(wǎng)絡(luò)達(dá)到k-連通。

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

定義1 如果存在兩個(gè)傳感器s和s'，使得d(s，p)=d(s'，p)=r，則把位置p 稱作放置中繼器的Pposition[2]。

算法的大體思想是這樣的，根據(jù)文獻(xiàn)5的思想，把傳感器和基站所在的區(qū)域劃分成若干個(gè)2r×ω的區(qū)域，這里所說(shuō)的滿足特定的條件指的是劃分的每個(gè)區(qū)域至少有一個(gè)傳感器，ω為算法分區(qū)因子，且為正整數(shù)，以ω=2為例來(lái)設(shè)計(jì)算法，把每個(gè)區(qū)域叫做分子。在介紹算法之前，先介紹一個(gè)概念。

在尋找所有放置中繼器的P-positions時(shí)，不一定所找到的P-positions 都在分子內(nèi)，給定一個(gè)分子Ti，P為所有P-positions的集合，對(duì)所有p∈P，如果p 不在Ti內(nèi)，用一個(gè)邊界上的點(diǎn)q 代替p，點(diǎn)q是Ti到p的最近的距離上的點(diǎn)，這樣的操作稱為收縮操作[2]。通過(guò)收縮操作，可以保證新的P-positions 都在區(qū)域內(nèi)，且同樣能覆蓋Ti中對(duì)應(yīng)的傳感器集。

算法1 k-覆蓋k-連通

步驟1 把X∪B 劃分成邊長(zhǎng)為4r的正方形分子，對(duì)每個(gè)分子，找到所有可以放置中繼器的P-positions，并將其收縮到區(qū)域內(nèi)。

步驟2 在每個(gè)分子內(nèi)，搜索X 中所有的放置中繼器的P-positions的12k-3個(gè)子集，找最小的至少能覆蓋分子內(nèi)每個(gè)傳感器k次的子集。

步驟3 對(duì)每個(gè)分子Ti，每個(gè)分子內(nèi)至少包含k個(gè)中繼器，如果Ti內(nèi)的中繼器不連通，則在距離A為4r的J，K 兩處放入兩個(gè)中繼器，在以A為圓心，4r為半徑，J，K為端點(diǎn)的圓弧上依次均勻的放入中繼器，當(dāng)k 較大時(shí)，可以在以B為圓心，4r為半徑，K，M為端點(diǎn)的圓弧上依次的放入中繼器，使網(wǎng)絡(luò)達(dá)到k-連通。

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

(1)使中繼器集Hi達(dá)到行k-連通，設(shè)Hi+1為Hi的右邊的中繼器集合，如果Hi+1和Hi不連通，則在Ti的J 處加入一個(gè)新的中繼器qi，Hi=Hi∪qi，如果Hi和Hi+1還是不連通，則在Ti+1的J 處(與A點(diǎn)距離為4r)放置一個(gè)新的中繼器qi+1，Hi+1=Hi+1∪qi+1;如果Hi和Hi+1沒(méi)有2 連通，則在Ti的K 處放置一個(gè)新的中繼器qi+2，Hi+1=Hi+1∪qi+2，如果Hi和Hi+1沒(méi)有2 連通，則在Ti+1的K 處放置一個(gè)新的中繼器qi+3，則Hi+1=Hi+1∪qi+3;重復(fù)以上步驟，直至所有的覆蓋分子的中繼器集與基站網(wǎng)絡(luò)都達(dá)到行k-連通;如果中繼器沒(méi)有達(dá)到k-連通，則在以A為圓心，4r為半徑，J，K為端點(diǎn)的圓弧上依次均勻的放入中繼器，以B為圓心，4r為半徑，K，M為端點(diǎn)的圓弧上依次均勻的放入中繼器，直到所有的中繼器都達(dá)到行k-連通。

(2)使中繼器集Hi與基站網(wǎng)絡(luò)都達(dá)到列k-連通。對(duì)每個(gè)分子Hi，LeftTi={q?Hi|q與覆蓋Ti左面相鄰分子的中繼器連通}，RightTi={q ?Hi|q與覆蓋Ti右面相鄰分子的中中繼器連通}，如果則有H'i=Hi，否則H'i=Hi-LeftTi∪RightTi。

如果H'i+y和H'i與不連通，則在Ti的J 處放置一個(gè)新的中繼器qi，Hi=Hi∪qi，接下來(lái)的步驟和為使中繼器達(dá)到行連通類似進(jìn)行。放置的規(guī)則如圖1所示:

圖1 區(qū)域劃分圖

首先可以由該算法的步驟2和4，得到算法1的時(shí)間復(fù)雜度為O (kn2)。

定理1算法1 在ω=2 下給出問(wèn)題k-覆蓋k-連通的一個(gè)解，且算法性能比為9/2。

證明 首先證明該算法得到的中繼器集是k-覆蓋k-連通的，由步驟1、2可以知道每個(gè)分子內(nèi)的傳感器至少被k個(gè)中繼器覆蓋，下面說(shuō)明中繼器集是k-連通的。

(1)每個(gè)分子內(nèi)的任意兩個(gè)中繼器是k-連通的。由步驟2，每個(gè)分子內(nèi)至少有k個(gè)中繼器，由步驟3，顯然每個(gè)分子內(nèi)的任意兩個(gè)中繼器都是k-連通的。

(2)任意兩個(gè)不在同一個(gè)分子內(nèi)的中繼器q，q'。假設(shè)q 在分子Ti中，q'在分子Ti+1中，為方便起見(jiàn)，設(shè)點(diǎn)q點(diǎn)在第i行第j列，q'在第i'行第j'列，假設(shè)i ＜i'，j ＜j'，并且假設(shè)Ti中存在同一個(gè)中繼器與Ti右邊及下面的分子內(nèi)的中繼器連通，則Ti中一定存在另外k-1 不相同的中繼器與其左邊的分子內(nèi)的中繼器連通，否則有LeftTi∪RightTi=k-1，于是q可以通過(guò)左右兩面k條不同的路徑達(dá)到q'點(diǎn)。

算法常數(shù)性能比為9/2的證明。設(shè)Ho為算法1 得到的最優(yōu)解，H'表示步驟1、2 產(chǎn)生的中繼器集合，即H' =∪Hi，設(shè)OPT為該問(wèn)題k-覆蓋的最優(yōu)解，根據(jù)Shifting 定理[5]有假定每個(gè)分子至少有一個(gè)傳感器，則H'至少包含k個(gè)中繼器，根據(jù)算法，每個(gè)分子至多額外加入k個(gè)中繼器，因此有所以

通過(guò)算法1 性能比的分析，發(fā)現(xiàn)運(yùn)用區(qū)域劃分思想放置中繼器的算法的性能比能達(dá)到一個(gè)很好的界，當(dāng)ω=2時(shí)k-覆蓋k-連通的上界為9/2，隨著k值的增大，性能比處于一個(gè)恒定的值，不發(fā)生變化。對(duì)不同的k值使用該算法，發(fā)現(xiàn)不管k值如何變化，所得到的問(wèn)題的算法的性能比均為常數(shù)9/2。

3 結(jié)束語(yǔ)

本文針對(duì)算法分區(qū)因子ω=2 設(shè)計(jì)k-覆蓋k-連通問(wèn)題的算法，證明了算法的性能比為9/2，時(shí)間復(fù)雜度為O (kn2)，本文只引用了算法分區(qū)因子等于2時(shí)的情況，是因?yàn)殡S著該值的增大，相應(yīng)的算法的時(shí)間復(fù)雜度也會(huì)提高。本文運(yùn)用區(qū)域劃分的思想，將雙層無(wú)線傳感網(wǎng)絡(luò)的中繼器放置問(wèn)題提高到了k-覆蓋k-連通，拓寬了無(wú)線傳感網(wǎng)絡(luò)問(wèn)題的研究領(lǐng)域。

[1]Hao B，Tang J，Xue G.Fault-tolerant relay node placement in wireless senor networks:Forrmulation and approximation[C].Michigan State:IEEE Workshop on High Performance Switching and Routing，2004:246-250.

[2]Tang J，Hao B，Sen A.Relay node placement in large scale wireless networks[J].Computer Communications，2006，29(7):490-501.

[3]崔素輝.無(wú)線傳感器網(wǎng)絡(luò)若干中繼器放置問(wèn)題[D].杭州:杭州電子科技大學(xué)，2009:30-35.

[4]Liu H，Wan P，Jia X.On Optimal Placement of Relay Nodes for Reliable Connectivity in Wireless Sensor Networks[J].Journal of Combinatorial Optimization，2006，11(2):249-260.

[5]Hochbaum D S，Maass W.Approximation schemes for covering and packing problems in image processing and VLSI[J].Journal of the ACM，1985，32(1):130-136.