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

0 引 言

無線傳感器網(wǎng)絡(luò)是由基站和大量價格低廉、能量較少的傳感器組成的。在無線傳感器網(wǎng)絡(luò)中，傳感器主要作用是感知周圍的環(huán)境，并把收集到的信息傳送給基站。傳感器節(jié)點在惡劣的環(huán)境中隨機的分布，能量只能由不能隨意更換的電池提供。但是能量消耗在長距離通訊中卻以距離指數(shù)的形式快速增加，所以研究者們提出了在無線傳感網(wǎng)絡(luò)中放置一定數(shù)目的中繼器的思路，這成為了減少能量損耗的重要方法。對單層網(wǎng)絡(luò)的2-連通問題，文獻1 設(shè)計了R=r 且不含基站情形的近似算法，并證明其性能比為10。當(dāng)R≥r時，文獻2 對不含基站和含有基站兩種情形分別設(shè)計了性能比為14和16的近似算法。本文研究含有基站的單層網(wǎng)絡(luò)2-連通問題，對R=r的情形設(shè)計了性能比為12的近似算法。

1 單層網(wǎng)絡(luò)2-連通問題的基本概念

B表示已知的基站集合，X表示已知的傳感器集合，Y表示放置的中繼器集合，并用d (x，y)表示平面上的點x和y的距離。假設(shè)傳感器的傳輸半徑為r，中繼器的傳輸半徑為R≥r。在單層無線傳感器網(wǎng)絡(luò)中，傳感器在傳輸半徑內(nèi)可以和中繼器、基站、其他傳感器傳輸數(shù)據(jù)，中繼器在傳輸半徑內(nèi)可以和基站、其他中繼器傳輸數(shù)據(jù)，這里都是假設(shè)基站的傳輸半徑足夠大，基站之間可以直接通訊。對給定的(R，r，B，X，Y)，構(gòu)造單層網(wǎng)絡(luò)上的混合無向連通圖HCG (R，r，B，X，Y)，其中頂點集為V=B∪X∪Y，邊集E 定義為:

(1)對任意兩個基站頂點bi，bj∈B，E 都包含無向邊(bi，bj)=(bj，bi);

(2)對任意中繼器頂點y∈Y以及頂點z∈Y∪B，如果d(y，z)≤R，則E 包含無向邊(y，z)=(z，y);

(3)對任意傳感器頂點x∈X以及頂點z∈X∪Y∪B，如果d(x，z)≤r，則E 包含無向邊(x，z)=(z，x)。

單層無線傳感器網(wǎng)絡(luò)的2-連通問題，就是要求放置最少數(shù)目的中繼器集合Y，使得圖HCG (R，r，B，X，Y)網(wǎng)絡(luò)中的任意兩個頂點之間至少存在兩條不相交的路，即保證該圖HCG (R，r，B，X，Y)是2-連通的。

當(dāng)R=r時，文獻1 證明了問題在不含基站的情形下已經(jīng)是NP-hard的，因此含有基站的情形也必是NP-hard的。

2 近似算法設(shè)計

首先，構(gòu)造由頂點集B∪X 導(dǎo)出的無向完全圖GC。對GC中任意兩頂點zi和zj(不全是基站頂點)，若它們的距離d(zi，zj)≤r，則它們在圖HCG 中直接相連。若d(zi，zj)＞r，則可以采取邊斯坦納化方法使之連通[3]。即在邊(zi，zj)上按照以下方式放置中繼器:

(1)如果r ＜d(zi，zj)≤2r，則在(zi，zj)的中間位置放入一個中繼器點;

(2)如果d(zi，zj)＞2r，則在(zi，zj)上放入兩個中繼器點yF，yL，使得d(zi，yF)=r，d(zj，yL)=r，再在邊(yF，yL)上均勻放置個中繼器。

邊(zi，zj)的權(quán)重c(zi，zj)如下易知c(zi，zj)恰是對邊(zi，zj)斯坦納化應(yīng)放置的中繼器數(shù)目，接下來給出2-連通問題的具體算法。

算法1 單層網(wǎng)絡(luò)2-連通問題。

輸入 傳感器集合X= {x1，x2，…，xn}，基站集合B= {b1，b2，…，bn}及常數(shù)R=r。

輸出 中繼器集合Y。

步驟1 由B∪X 構(gòu)建無向完全圖GC。

步驟2 對GC中的每條邊(zi，zj)賦權(quán)重c(zi，zj)。

步驟3 利用文獻4中的算法得到GC的一個2-連通生成子圖G'C。

步驟4 在G'C的每條邊上按邊斯坦納化方法放置中繼器，并把這些頂點加到集合Y中，構(gòu)建圖HCG (R，r，B，X，Y)。

3 算法性能比分析

在傳感器頂點和基站頂點之間放置的中繼器稱為珠子，最優(yōu)解放置的中繼器稱為斯坦納點，S表示全部的斯坦納點個數(shù)。主要結(jié)論是下述定理:

定理1算法1 得到的2-連通網(wǎng)絡(luò)最多需要放置12S 珠子，即性能比為12。

為證明定理，接下來先給出幾個重要的引理。

引理1 在2-連通的中繼器放置無線傳感器網(wǎng)絡(luò)中，與任意一個中繼器相連的傳感器個數(shù)不超過5[5]，與任意一個中繼器相連的基站個數(shù)不超過1[2]。

引理2 終點集B∪X 導(dǎo)出的賦權(quán)完全圖GC的最小2-連通子圖的權(quán)重不超過6S，即由此產(chǎn)生的2-連通網(wǎng)絡(luò)中至多有6S個珠子。

證明 令G0=(V0，E0)為放置最少數(shù)目中繼器構(gòu)成的最優(yōu)2-連通網(wǎng)絡(luò)，即其中的中繼器均為斯坦納點。接下來構(gòu)建只含有珠子而不含有斯坦納點的2-連通網(wǎng)絡(luò)Gm(m≥1)，證明網(wǎng)絡(luò)中最多含有6S個珠子。

從j=1 開始，由Gj-1構(gòu)造Gj，具體過程如下:

第一步 找出G0中由斯坦納點構(gòu)成的連通分支SCi(1≤i≤m)，然后對于每個連通分支找出度數(shù)之和最小的支撐樹ST1，ST2，…，STm，如圖1所示;

第二步 用Hj表示STj與其傳輸范圍內(nèi)的終點集Vj構(gòu)成的樹，如圖2所示;

第三步 找出Hj中邊數(shù)最多的路徑，以該路的一端點t1(必為葉子頂點)為樹的根，計算樹上其余頂點到根之間的邊數(shù)，定義為該頂點的深度。按照深度優(yōu)先搜索法，從t1開始遍歷Hj的所有葉子頂點，即終點集。按遍歷先后順序連接所有的終點，得到一個終點集構(gòu)成的圈，如圖3所示;

第四步 去掉Hj中的斯坦納點，并終點集構(gòu)成的圈的每條邊上按照邊斯坦納化方法放置中繼器(珠子)。從而，包含珠子的圈上任意兩點之間均存在2條不相交的路，如圖4所示。

圖1 最小的支撐樹STj

圖2 斯坦納點與終點構(gòu)成的樹Hj

圖3 終點集Vj 構(gòu)成的圈

圖4 去掉斯坦納點

從Gj-1構(gòu)造Gj，就是從Gj-1去掉STj中斯坦納點集及其相連接的邊集，然后把由Vj生成的圈放入Gj-1，便得到Gj。因此，最后可以得到只含有珠子而不含有斯坦納點的2-連通網(wǎng)絡(luò)Gm。

用bj表示從Gj-1構(gòu)造Gj過程中增加的珠子個數(shù)，Sj表示STj中的斯坦納點個數(shù)，b表示構(gòu)造網(wǎng)絡(luò)Gm整個過程所需要增加的珠子總數(shù)。注意到樹STj中經(jīng)過同一個斯坦納點的兩條邊的夾角均不小于60°[6]，所以任意兩個終點相連所需放置的珠子個數(shù)不會超過遍歷搜索的斯坦納點個數(shù)，如圖5所示，圖5(a)、(b)、(c)分別表示1個斯坦納點、2個斯坦納點及n個斯坦納點的情形。結(jié)合根據(jù)引理1，可知終點個數(shù)最多為6Sj，即bj≤5Sj+Sj=6Sj，于是總的放入的珠子數(shù)目為引理2 得證。

圖5 兩個終點相連的情況

接下來給出定理1的證明。

證明 注意到算法1 在第3步中利用了文獻4的算法去尋找最小2-連通生成子圖，由于該算法的性能比不超過2[4]，而按照引理2，放置珠子的數(shù)目為斯坦納點的6倍，于是算法1 需要加入的珠子至多為斯坦納點的2×6 =12倍，定理1 得證。

4 結(jié)束語

本文主要研究了含有基站的單層網(wǎng)絡(luò)的中繼器放置問題。對單層無線傳感器網(wǎng)絡(luò)2-連通問題，設(shè)計了R=r 情形的近似算法，性能比為12，這是一個新結(jié)果。

[1]Kashyap A，Khuller S，Shayman M.Relay placement for higher order connectivity in wireless sensor networks[C].Barcelona:IEEE International Conference on Computer Communications，2006:1-12.

[2]Zhang W，Xue G，Misra S.Fault-Tolerant Relay Node Placement in Wireless Sensor Networks:Problems and Algorithms[C].Anchorage∶IEEE International Conference on Computer Communications，2007:1 649-1 659.

[3]Lin G，Xue G.Steiner tree problem with minimum number of Steiner point and bounded edge-length[J].Information Processing Letters，1999，69(2):53-57.

[4]Khuller S，Raghavachari B.Improved approximation algorithms for uniform connectivity problems[C].New York:the twenty-seventh annual ACM symposium on Theory of computing，1995∶214-235.

[5]Monma C，Suri S.Transitions in geometric minimum spanning tree[J].Discrete and Computational Geometry，1992，8(1):265-293.

[6]Chen D，Wang L，Xue G.Approximations for steiner trees with minimum number of steiner points[J].Journal of Global Optimization，2000，18(1):17-33.