WSN中一種改進的節(jié)點部署方案

張 凱

(武漢理工大學(xué)信息工程學(xué)院，湖北武漢 430070)

0 引言

無線傳感器網(wǎng)絡(luò)是近年來受到國內(nèi)外廣泛關(guān)注的研究熱點。在工作過程中節(jié)點會不斷地感知到周邊環(huán)境的數(shù)據(jù)，并將通過無線天線將數(shù)據(jù)以多跳的方式發(fā)送給遠(yuǎn)方的Sink節(jié)點(或稱為基站)進行處理，節(jié)點的部署方案將直接影響數(shù)據(jù)收集和網(wǎng)絡(luò)生存期等性能。因此，如何有效地對節(jié)點進行部署［1］成為無線傳感網(wǎng)進行數(shù)據(jù)收集和處理的關(guān)鍵。

1 相關(guān)工作

目前，對于無線傳感網(wǎng)的節(jié)點部署研究工作較多，文獻［2］針對傳感器網(wǎng)絡(luò)節(jié)點部署時首要考慮的是覆蓋問題，提出一種可以滿足不同覆蓋率要求的節(jié)點優(yōu)化部署算法，在提高節(jié)點覆蓋性能的同時優(yōu)化節(jié)點數(shù)量，降低網(wǎng)絡(luò)的配置代價。仿真結(jié)果證明，該算法可最大化節(jié)點的覆蓋效率;文獻［3］為提高無線傳感器網(wǎng)絡(luò)的節(jié)點覆蓋度，提出一種目標(biāo)關(guān)聯(lián)覆蓋算法，利用節(jié)點間的關(guān)聯(lián)性和動態(tài)分組調(diào)整覆蓋區(qū)域，利用貪心算法對覆蓋區(qū)域進行優(yōu)化，以保證所關(guān)注的目標(biāo)節(jié)點被傳感器節(jié)點均勻覆蓋，同時提高網(wǎng)絡(luò)資源的利用率。在每個周期內(nèi)喚醒部分節(jié)點，輪流進行工作，以均衡網(wǎng)絡(luò)能量消耗。實驗結(jié)果表明，該算法適應(yīng)性更強，并且能有效降低網(wǎng)絡(luò)能耗，提高網(wǎng)絡(luò)性能;文獻［4］針對現(xiàn)有的節(jié)點調(diào)度算法不能同時保證工作節(jié)點均勻分布，使網(wǎng)絡(luò)能耗不均衡的問題，提出了一種與節(jié)點位置無關(guān)的無線傳感器網(wǎng)絡(luò)覆蓋協(xié)議(EBLCP)。EBLCP在虛擬坐標(biāo)的基礎(chǔ)上建立臨時集，節(jié)點只需與鄰居中少量節(jié)點通信，比較這些節(jié)點的剩余能量從而競選工作節(jié)點。實驗結(jié)果表明，EBLCP能保證較高的覆蓋率，并延長網(wǎng)絡(luò)生存時間。然而，以上的部署算法都是建立在節(jié)點的感知范圍無邊界或者邊界效應(yīng)可以忽略的假設(shè)上。事實上，在實際的場景中，邊界的存在對于網(wǎng)絡(luò)的連通覆蓋具有重大的影響，而現(xiàn)有的“修補”方法雖然可以保證連通覆蓋薄弱區(qū)域，但是卻提高了網(wǎng)絡(luò)部署的成本，并會造成節(jié)點分布不均勻的狀況。針對以上問題，提出了一種改進的無線傳感器節(jié)點部署算法，理論分析和仿真實驗表明，所提出的方案是有效的。

2 相關(guān)定義與建模分析

2.1 相關(guān)定義

令CN表示節(jié)點N的覆蓋范圍，⊙N表示節(jié)點N覆蓋圓的圓周。A，B，C，D，E 為凸邊形的頂點，如圖1所示。

圖1 凸角多邊形abcde的定義

定義1 內(nèi)分點(IPD):指凸多邊形的內(nèi)部任一頂點中，位于其他頂點的內(nèi)角平分線上且與其他頂點的歐式距離為d的點，d∈［0，rN］。如圖1中點A1，B1，C1，D1，E1。

定義2 邊界線(BL):指從一個內(nèi)分點到另一個內(nèi)分點所做的平行于邊界的直線。

定義3 邊界點(BP):指位于邊界線上除內(nèi)分點以外的其他所有頂點。

定義4 邊角交點(IPF):角點的感應(yīng)圓圈與邊點線的交點。

2.2 網(wǎng)絡(luò)模型

將監(jiān)測區(qū)域π模擬為二維平面內(nèi)的不規(guī)則凸角多邊形δ，邊界信息已知，凸角多邊形其邊界頂點位置依據(jù)順時針方向標(biāo)記為 {a，b，c…}。這里假設(shè)無線傳感網(wǎng)具有以下性質(zhì):

①所有節(jié)點部署后保持靜止，不再移動;

②所有節(jié)點以自身為圓心，在其感知范圍為進行感知，所有節(jié)點的感知半徑一致，均為rsame;

③ 對于任意節(jié)點x，y而言，僅當(dāng)d(x，y)≤rsame時，則認(rèn)為節(jié)點x被節(jié)點y覆蓋。d(x，y)表示2個節(jié)點間的歐式距離。

3 改進的部署方案

本文提出的改進的節(jié)點部署方案命名為IDS。它主要由2個部分組成:首先，對于感知區(qū)域進行邊界的部署，達到保證全連通和覆蓋的效果，然后在感知區(qū)域內(nèi)，通過凸多邊形生成算法來不斷地進行內(nèi)部部署，遞歸調(diào)用知道整個感知區(qū)域被覆蓋。

3.1 邊界部署

邊界部署的主要目的是保證部署后的節(jié)點能夠覆蓋整個感知區(qū)域的邊界。部署過程如下:①根據(jù)δ的頂點信息，確定對應(yīng)δ每個凸角的角度和角點;②確定與每個內(nèi)分點對應(yīng)的邊界線;③依據(jù)式(1)和式(2)來確定每條邊界線上的邊界點［1］。

3.2 新凸邊形的生成

邊界部署完成后，δ并沒有被完全覆蓋，生成了多個邊角交點IPF，如圖2所示。

圖2 邊界的生成

由于現(xiàn)在未被覆蓋區(qū)域的邊界形狀變得更加復(fù)雜，因此GRLD算法的第2部分旨在生成新的邊界，形成新的凸多邊形區(qū)域。思想如下:過每個IPF做平行于對應(yīng)邊界的平行線，以這些平行線的交點為新的頂點，順時針連接形成新的凸角多邊形。

3.2.1 算法2:新凸邊形生成算法

3.2.2 算法3:改進后的部署算法

結(jié)合算法1和算法2遞歸調(diào)用，即得到本文提出的IDS算法如下:

4 仿真實驗

這里使用MATLAB2011對IDS進行仿真實驗，并與目前較為典型的部署方案(六邊形點陣和四邊形點陣)進行了性能比較分析。實驗過程中，節(jié)點的感應(yīng)半徑設(shè)定為5 m，通信半徑設(shè)為10 m。實驗結(jié)果如圖3(a)所示。

實驗結(jié)果是當(dāng)感應(yīng)區(qū)域為三角形、四邊形、六邊形和任意形狀時，使用IDS、六邊形點陣和四邊形點陣進行部署時，所需要使用到的節(jié)點個數(shù)比較。結(jié)果表明，就達到完全覆蓋效果上來看，IDS使用的節(jié)點個數(shù)是最少的。這主要是因為，IDS方案從邊界開始布點，克服了部署后“修補”薄弱區(qū)域所需要的節(jié)點，從而大大減少了節(jié)點感應(yīng)區(qū)域的疊加，增大節(jié)點的有效覆蓋面積，使得浪費減少。

圖3 不同部署方案的節(jié)點個數(shù)變化

圖3(b)表示的是放感知區(qū)域面積變化時，使用IDS、六邊形點陣和四邊形點陣部署的節(jié)點個數(shù)變化情況，從中可以看出，當(dāng)δ的面積從4320 m2增大到67500 m2時，IDS所需的節(jié)點個數(shù)的增幅為1500個，六邊形點陣下所需的節(jié)點個數(shù)的增幅為2100，四邊形點陣下的節(jié)點增幅為2400個。即IDS只需要增加較少數(shù)量的節(jié)點就能達到和六邊形點陣有更小的節(jié)點增幅，說明其相對于四邊形點陣、四邊形點陣一樣的覆蓋效果，因此本文的方法更容易擴展，穩(wěn)定性更好。

5 結(jié)束語

如何有效地部署傳感網(wǎng)節(jié)點對于提高無線傳感網(wǎng)的數(shù)據(jù)傳輸質(zhì)量以及延長網(wǎng)絡(luò)生命周期具有重要的影響。在傳統(tǒng)的部署算法上，進一步考慮了邊界效應(yīng)對于網(wǎng)絡(luò)連通和覆蓋的影響，提出了一種改進的節(jié)點部署方案IDS。理論分析和仿真實驗表明，本文方法是有效的，相比于六邊形點陣和四邊形點陣的部署效果而言，IDS所需使用的節(jié)點個數(shù)也更少，且算法更容易擴展。下一步的工作是對現(xiàn)有的部署方案進行拓展，研究三維區(qū)域內(nèi)的確定性部署方案。 ■

［1］LIAO Z，WANG J，WANG X，et al.GRLD:A Seamless Growth Rings like Deployment of Sensors Avoiding Boundary Effects in WSNs［C］∥Wireless Communications and Networking Conference(WCNC)，IEEE，2010:1 －6.

［2］孫澤宇，邢蕭飛，魏 巍.無線傳感器網(wǎng)絡(luò)中的目標(biāo)關(guān)聯(lián)覆蓋算法［J］.計算機工程，2011，37(9):138 －140.

［3］朱繼華，武 俊，陶 洋.基于覆蓋率的傳感器優(yōu)化部署算法［J］.計算機工程，2011，36(3):94 －96.

［4］孫澤宇，邢蕭飛，魏 巍.無線傳感器網(wǎng)絡(luò)中的目標(biāo)關(guān)聯(lián)覆蓋算法［J］.計算機工程，2011，37(9):138 －140.

［5］ZHANGH，HOU J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］.Ad Hoc ＆Sensor Wireless Networks，2005，1(1):89 －124.

［6］IYENGARR，KAR K，BANERJEE S.Low-coordination Topologies for Redundancy in Sensor Networks［C］∥The 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2005:332 －342.

［7］BAIX，XUAN D，YUN Z，etal.Complete Optimal Deployment Patterns for Full-coverage and k-connectivity(k≤6)［C］∥The 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2008:401－410.

［8］WANG X，SUN F，KONG X.Research on Optimal Coverage Problem of Wireless Sensor Networks［C］∥International Conference on Communications and Mobile Computing，2009:548－551.