無(wú)線傳感器網(wǎng)絡(luò)覆蓋連通性研究

1引言

集成傳感器技術(shù)、微機(jī)電系統(tǒng)（MEMS）技術(shù)、無(wú)線通信技術(shù)和分布式信息處理技術(shù)的無(wú)線傳感器網(wǎng)絡(luò)（WSN,wirelesssensornetworks）是當(dāng)前信息技術(shù)的前沿之一，也是當(dāng)今的研究熱點(diǎn)，受到了廣泛的關(guān)注。目前，無(wú)線傳感器網(wǎng)絡(luò)逐漸成為一種廉價(jià)、方便的信息采集方法，尤其是在敵對(duì)和惡劣的網(wǎng)絡(luò)應(yīng)用環(huán)境下，傳統(tǒng)的方法代價(jià)高昂而幾乎無(wú)法使用。如文獻(xiàn)[1~3]中的戰(zhàn)場(chǎng)生存性應(yīng)用、一些安全相關(guān)的應(yīng)用以及災(zāi)難管理等應(yīng)用，無(wú)線傳感器網(wǎng)絡(luò)都顯示了巨大的應(yīng)用價(jià)值。在上述應(yīng)用中，傳感器節(jié)點(diǎn)往往是隨機(jī)地部署在監(jiān)測(cè)區(qū)域，一直工作到能量耗盡為止。

無(wú)線傳感器網(wǎng)絡(luò)部署之后，傳感器節(jié)點(diǎn)采集現(xiàn)實(shí)生活中諸如熱、光或者某個(gè)監(jiān)測(cè)對(duì)象的相關(guān)物理信息，對(duì)于傳感器網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)，都通過(guò)自身的傳感電路感知監(jiān)測(cè)對(duì)象的相關(guān)信息，獲取原始數(shù)據(jù)，然后通過(guò)一類稱為基站的特殊節(jié)點(diǎn)經(jīng)過(guò)相應(yīng)處理并傳送到外界的控制中心。在傳感器網(wǎng)絡(luò)中，基站的能量和處理能力都較普通節(jié)點(diǎn)強(qiáng)，基站在網(wǎng)絡(luò)部署時(shí)基本部署在其他傳感器節(jié)點(diǎn)的附近，其功能是在傳感數(shù)據(jù)傳送到外界控制中心之前對(duì)其進(jìn)行相應(yīng)的處理，如通過(guò)數(shù)據(jù)匯聚和融合，基站過(guò)濾掉原始傳感數(shù)據(jù)中一些錯(cuò)誤和無(wú)效的數(shù)據(jù)，并消除冗余數(shù)據(jù)，同時(shí)，基站也會(huì)定期對(duì)傳感數(shù)據(jù)進(jìn)行匯總處理。在文獻(xiàn)[4]的傳感器網(wǎng)絡(luò)應(yīng)用中，經(jīng)過(guò)基站融合后的傳感數(shù)據(jù)可以有效地用來(lái)追蹤和識(shí)別監(jiān)測(cè)目標(biāo)；在一些災(zāi)難急救的傳感器網(wǎng)絡(luò)應(yīng)用中，融合后的傳感數(shù)據(jù)可以有效地預(yù)測(cè)幸存者的健康狀況以及遇難者的準(zhǔn)確位置信息等。

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署之后，如何保證網(wǎng)絡(luò)的連通性一直是研究界非常關(guān)注的問(wèn)題，國(guó)內(nèi)外研究界提出了一些相關(guān)的算法和協(xié)議，比較有代表性的有：文獻(xiàn)[5]集中討論了傳感器感知模型非圓時(shí)網(wǎng)絡(luò)覆蓋和連通性之間的關(guān)系；文獻(xiàn)[6,7]針對(duì)網(wǎng)絡(luò)的使用壽命問(wèn)題，研究了如何在部署的網(wǎng)絡(luò)節(jié)點(diǎn)中選擇足夠的節(jié)點(diǎn)以構(gòu)成網(wǎng)絡(luò)的覆蓋連通集；文獻(xiàn)[8]討論了在對(duì)部署節(jié)點(diǎn)位置信息未知的情況下，如何能有效地保證網(wǎng)絡(luò)連通性覆蓋的問(wèn)題；在文獻(xiàn)[9]中，詳細(xì)研究了不同情況下的傳感器網(wǎng)絡(luò)覆蓋連通性的分析方法；文獻(xiàn)[10]給出了一種改進(jìn)的傳感器節(jié)點(diǎn)覆蓋優(yōu)化方法。

針對(duì)傳感器網(wǎng)絡(luò)的覆蓋連通性問(wèn)題，本文將在第2節(jié)討論無(wú)線傳感器網(wǎng)絡(luò)覆蓋連通性理論及網(wǎng)絡(luò)模型。第3節(jié)采用了一種節(jié)點(diǎn)代理基站來(lái)解決網(wǎng)絡(luò)中不可達(dá)節(jié)點(diǎn)的連通性方案。第4節(jié)將給出在第2節(jié)中所給模型的基礎(chǔ)上進(jìn)行網(wǎng)絡(luò)覆蓋連通性判定的算法。第5節(jié)對(duì)提出的基站代理方案和節(jié)點(diǎn)連通性判定算法進(jìn)行實(shí)驗(yàn)。第6節(jié)是結(jié)束語(yǔ)。

2網(wǎng)絡(luò)覆蓋連通性理論及網(wǎng)絡(luò)模型

傳感器網(wǎng)絡(luò)節(jié)點(diǎn)連通性的要求與adhoc網(wǎng)絡(luò)大致一致：1)信息必須有一條或足夠多的路徑從信息源轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)(基站)；2)信息在轉(zhuǎn)發(fā)過(guò)程中延遲盡量小。信息的轉(zhuǎn)發(fā)路徑越多，系統(tǒng)越可靠，但由于需要多個(gè)中間節(jié)點(diǎn)同時(shí)處于工作狀態(tài)，節(jié)點(diǎn)能耗增加，系統(tǒng)壽命降低。無(wú)線發(fā)射器件的能耗隨著收發(fā)距離長(zhǎng)度的變大呈指數(shù)增長(zhǎng)，采用多跳方式信息轉(zhuǎn)發(fā)代替點(diǎn)對(duì)點(diǎn)通信，可以節(jié)約大量的能量。但過(guò)多的跳數(shù)會(huì)增加信息接收轉(zhuǎn)發(fā)的次數(shù)，同樣會(huì)帶來(lái)額外的能耗。因此，將上述2個(gè)矛盾的因素折衷，適當(dāng)控制轉(zhuǎn)發(fā)節(jié)點(diǎn)的個(gè)數(shù)是降低能耗的關(guān)鍵。

通常，理想狀態(tài)下具有節(jié)點(diǎn)連通性優(yōu)化作用的密度控制所要解決的核心問(wèn)題同覆蓋優(yōu)化類似，但節(jié)點(diǎn)的約束條件更多。將所有傳感節(jié)點(diǎn)組成的集合分為｛h1,h2,…,hm｝等m個(gè)子集，即，設(shè)hi為組成主干連接網(wǎng)絡(luò)的傳感節(jié)點(diǎn)的一個(gè)集合，si是傳感器節(jié)點(diǎn)。每個(gè)處于傳感狀態(tài)的非主干節(jié)點(diǎn)能夠與至少一個(gè)主干節(jié)點(diǎn)通信，主干節(jié)點(diǎn)之間必須有一條且至少一條直接或間接的路徑實(shí)現(xiàn)二者相連。

基于上述理論，給出一個(gè)一般意義上的無(wú)線傳感器網(wǎng)絡(luò)模型，描述如下。

設(shè)N個(gè)傳感器節(jié)點(diǎn)隨機(jī)地部署在某一區(qū)域，節(jié)點(diǎn)擁有有限的電池能量和數(shù)據(jù)處理能力，在網(wǎng)絡(luò)應(yīng)用中節(jié)點(diǎn)的任務(wù)是按照外界控制中心的需要進(jìn)行動(dòng)態(tài)的工作，基站部署在其他傳感器節(jié)點(diǎn)附近。假設(shè)傳感器節(jié)點(diǎn)和基站都處于靜止?fàn)顟B(tài)，且基站可以獲悉其他節(jié)點(diǎn)的位置信息?；静捎梦墨I(xiàn)[11,12]中的beacons信號(hào)在網(wǎng)絡(luò)觸發(fā)階段發(fā)現(xiàn)活動(dòng)節(jié)點(diǎn)，基站負(fù)責(zé)組織協(xié)調(diào)傳感器節(jié)點(diǎn)采集相關(guān)監(jiān)測(cè)數(shù)據(jù)，匯聚融合原始傳感數(shù)據(jù)并與外界控制中心進(jìn)行聯(lián)系，最后由控制中心把處理完的有用信息傳遞給用戶。

在系統(tǒng)模型中，設(shè)傳感器節(jié)點(diǎn)能夠向基站報(bào)告其剩余能量信息，并能智能地切換開(kāi)啟和休眠狀態(tài)，且傳感電路和數(shù)據(jù)處理電路可以智能開(kāi)關(guān)，另外，節(jié)點(diǎn)傳輸距離可以通過(guò)編程進(jìn)行調(diào)節(jié)控制。值得注意的是，SenTech公司開(kāi)發(fā)的聲覺(jué)通道模塊[13]傳感器節(jié)點(diǎn)具有上述功能。設(shè)傳感器節(jié)點(diǎn)可以作為數(shù)據(jù)轉(zhuǎn)發(fā)的中繼?；緭碛锌梢愿鶕?jù)實(shí)際任務(wù)和環(huán)境的需要智能地選取部分傳感器節(jié)點(diǎn)進(jìn)行工作、選擇數(shù)據(jù)路由以及媒體訪問(wèn)仲裁的網(wǎng)絡(luò)管理功能。在網(wǎng)絡(luò)系統(tǒng)模型中，網(wǎng)絡(luò)的組織和管理都是基于能量意識(shí)的，依賴于每個(gè)傳感器節(jié)點(diǎn)的能量知識(shí)，網(wǎng)絡(luò)的控制參照傳感器節(jié)點(diǎn)的工作狀況和能量剩余情況。

在系統(tǒng)中，參考文獻(xiàn)[14,15]中節(jié)點(diǎn)通信時(shí)的能量消耗模型，模型中定義的節(jié)點(diǎn)發(fā)送信息和接受信息的能量消耗公式如下。

發(fā)送信息能量消耗：， 接收信息能量消耗：， 其中，Es表示節(jié)點(diǎn)發(fā)送消息的能量消耗；β1和β2分別表示節(jié)點(diǎn)在發(fā)送和接收信息過(guò)程中單位信息所耗損的能量，其值均取為50nJ/bit；β’表示單位信息在傳送過(guò)程中由于信號(hào)保持而在單位面積(m2)耗損的能量，其值取為100pJ/bit/ m2；m表示信息位數(shù)；d表示信息傳輸距離。

基于以上無(wú)線傳感器網(wǎng)絡(luò)的系統(tǒng)模型，給出以下一些定義。

定義1傳感器節(jié)點(diǎn)間的連通性。若在無(wú)線傳感器網(wǎng)絡(luò)部署區(qū)域內(nèi)，節(jié)點(diǎn)之間總可以某種路由方式相互傳送信息，則稱在網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)節(jié)點(diǎn)之間是連通的。

定義2無(wú)線傳感器網(wǎng)絡(luò)的連通性。若在無(wú)線傳感器網(wǎng)絡(luò)部署區(qū)域內(nèi)，對(duì)于所有節(jié)點(diǎn)的極大子集，基站總是可以某種路由方式傳送相關(guān)控制信息到該節(jié)點(diǎn)集合中的任何節(jié)點(diǎn)，且該節(jié)點(diǎn)集合中的任意節(jié)點(diǎn)間也是連通的，則稱在該網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)由此極大節(jié)點(diǎn)子集組成的無(wú)線傳感器網(wǎng)絡(luò)是連通的。

在無(wú)線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的能量主要花費(fèi)在對(duì)外界信號(hào)的轉(zhuǎn)換處理和進(jìn)行數(shù)據(jù)通信的開(kāi)銷方面。由于節(jié)點(diǎn)的能量是由有限的電池提供，如果在網(wǎng)絡(luò)工作時(shí)一直讓節(jié)點(diǎn)在任何情況下都處于開(kāi)啟狀態(tài)則會(huì)降低節(jié)點(diǎn)的使用壽命，從而影響整個(gè)網(wǎng)絡(luò)的使用壽命。因此，如何有效地利用基站優(yōu)化組織和管理無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)的優(yōu)化應(yīng)用具有重要的意義。一類面向任務(wù)的傳感器網(wǎng)絡(luò)應(yīng)用可以選擇性地開(kāi)啟覆蓋區(qū)域內(nèi)的傳感器節(jié)點(diǎn)并平衡節(jié)點(diǎn)的負(fù)載，對(duì)于任務(wù)無(wú)關(guān)的節(jié)點(diǎn)使其處于休眠狀態(tài)，這樣可以節(jié)約寶貴的傳感器節(jié)點(diǎn)能量，達(dá)到延長(zhǎng)節(jié)點(diǎn)乃至整個(gè)網(wǎng)絡(luò)壽命的目的。

上述網(wǎng)絡(luò)優(yōu)化過(guò)程的前提是基站必須獲悉網(wǎng)絡(luò)中節(jié)點(diǎn)情況，只有確保覆蓋區(qū)域內(nèi)網(wǎng)絡(luò)節(jié)點(diǎn)的連通性基站才能有效地對(duì)節(jié)點(diǎn)進(jìn)行組織和管理。在傳感器網(wǎng)絡(luò)通信中，節(jié)點(diǎn)與基站之間理想通信模式是使用短距離的通信方式，這種方式假設(shè)基站對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)在任何情況下都是可達(dá)的，然而，這并不符合實(shí)際。因?yàn)樵诓渴饌鞲衅骶W(wǎng)絡(luò)時(shí)沒(méi)有統(tǒng)一的模式，且網(wǎng)絡(luò)部署環(huán)境有很大差別。在許多實(shí)際應(yīng)用場(chǎng)景中存在各種障礙物（如建筑物、樹(shù)木以及其他一些干擾信號(hào)等）會(huì)阻礙節(jié)點(diǎn)和基站之間的正常通信，有時(shí)這些障礙物甚至?xí)构?jié)點(diǎn)處于不可用狀態(tài)。

圖1描述的是當(dāng)基站和傳感器節(jié)點(diǎn)都處于彼此的通信范圍內(nèi)時(shí)，由于障礙物的存在使得基站不能夠與被阻礙節(jié)點(diǎn)進(jìn)行直接通信的情況。

對(duì)于基站和傳感器節(jié)點(diǎn)不能直接通信的另一種情況如圖2所示，在傳感器網(wǎng)絡(luò)部署區(qū)域內(nèi)，有部分節(jié)點(diǎn)處于基站的傳輸范圍之外，此時(shí)基站和這部分節(jié)點(diǎn)就不能進(jìn)行直接通信。