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

0 引 言

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

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

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

(1)對(duì)任意兩個(gè)基站頂點(diǎn)bi，bj∈B，E 都包含無(wú)向邊(bi，bj)=(bj，bi);

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

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

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

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

2 近似算法設(shè)計(jì)

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

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

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

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

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

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

輸出 中繼器集合Y。

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

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

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

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

3 算法性能比分析

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

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

為證明定理，接下來(lái)先給出幾個(gè)重要的引理。

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

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

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

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

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

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

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

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

圖1 最小的支撐樹STj

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

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

圖4 去掉斯坦納點(diǎn)

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

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

圖5 兩個(gè)終點(diǎn)相連的情況

接下來(lái)給出定理1的證明。

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

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

本文主要研究了含有基站的單層網(wǎng)絡(luò)的中繼器放置問(wèn)題。對(duì)單層無(wú)線傳感器網(wǎng)絡(luò)2-連通問(wèn)題，設(shè)計(jì)了R=r 情形的近似算法，性能比為12，這是一個(gè)新結(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.