本文講述的重點(diǎn)就是無線傳感器網(wǎng)絡(luò)，目的就是要告訴大家有關(guān)無線傳感器網(wǎng)絡(luò)的特點(diǎn)及原理。

無線傳感器網(wǎng)絡(luò)部署之后，傳感器節(jié)點(diǎn)采集現(xiàn)實(shí)生活中諸如熱、光或者某個(gè)監(jiān)測對象的相關(guān)物理信息，對于傳感器網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)，都通過自身的傳感電路感知監(jiān)測對象的相關(guān)信息，獲取原始數(shù)據(jù)，然后通過一類稱為基站的特殊節(jié)點(diǎn)經(jīng)過相應(yīng)處理并傳送到外界的控制中心。在傳感器網(wǎng)絡(luò)中，基站的能量和處理能力都較普通節(jié)點(diǎn)強(qiáng)，基站在網(wǎng)絡(luò)部署時(shí)基本部署在其他傳感器節(jié)點(diǎn)的附近，其功能是在傳感數(shù)據(jù)傳送到外界控制中心之前對其進(jìn)行相應(yīng)的處理，如通過數(shù)據(jù)匯聚和融合，基站過濾掉原始傳感數(shù)據(jù)中一些錯(cuò)誤和無效的數(shù)據(jù)，并消除冗余數(shù)據(jù)，同時(shí)，基站也會(huì)定期對傳感數(shù)據(jù)進(jìn)行匯總處理。在文獻(xiàn)[4]的傳感器網(wǎng)絡(luò)應(yīng)用中，經(jīng)過基站融合后的傳感數(shù)據(jù)可以有效地用來追蹤和識(shí)別監(jiān)測目標(biāo)；在一些災(zāi)難急救的傳感器網(wǎng)絡(luò)應(yīng)用中，融合后的傳感數(shù)據(jù)可以有效地預(yù)測幸存者的健康狀況以及遇難者的準(zhǔn)確位置信息等。
    
    傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署之后，如何保證網(wǎng)絡(luò)的連通性一直是研究界非常關(guān)注的問題，國內(nèi)外研究界提出了一些相關(guān)的算法和協(xié)議，比較有代表性的有：文獻(xiàn)[5]集中討論了傳感器感知模型非圓時(shí)網(wǎng)絡(luò)覆蓋和連通性之間的關(guān)系；文獻(xiàn)[6,7]針對網(wǎng)絡(luò)的使用壽命問題，研究了如何在部署的網(wǎng)絡(luò)節(jié)點(diǎn)中選擇足夠的節(jié)點(diǎn)以構(gòu)成網(wǎng)絡(luò)的覆蓋連通集；文獻(xiàn)[8]討論了在對部署節(jié)點(diǎn)位置信息未知的情況下，如何能有效地保證網(wǎng)絡(luò)連通性覆蓋的問題；在文獻(xiàn)[9]中，詳細(xì)研究了不同情況下的傳感器網(wǎng)絡(luò)覆蓋連通性的分析方法；文獻(xiàn)[10]給出了一種改進(jìn)的傳感器節(jié)點(diǎn)覆蓋優(yōu)化方法。
   
    針對傳感器網(wǎng)絡(luò)的覆蓋連通性問題，本文將在第2節(jié)討論無線傳感器網(wǎng)絡(luò)覆蓋連通性理論及網(wǎng)絡(luò)模型。第3節(jié)采用了一種節(jié)點(diǎn)代理基站來解決網(wǎng)絡(luò)中不可達(dá)節(jié)點(diǎn)的連通性方案。第4節(jié)將給出在第2節(jié)中所給模型的基礎(chǔ)上進(jìn)行網(wǎng)絡(luò)覆蓋連通性判定的算法。第5節(jié)對提出的基站代理方案和節(jié)點(diǎn)連通性判定算法進(jìn)行實(shí)驗(yàn)。第6節(jié)是結(jié)束語。
   
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ā)過程中延遲盡量小。信息的轉(zhuǎn)發(fā)路徑越多，系統(tǒng)越可靠，但由于需要多個(gè)中間節(jié)點(diǎn)同時(shí)處于工作狀態(tài)，節(jié)點(diǎn)能耗增加，系統(tǒng)壽命降低。無線發(fā)射器件的能耗隨著收發(fā)距離長度的變大呈指數(shù)增長，采用多跳方式信息轉(zhuǎn)發(fā)代替點(diǎn)對點(diǎn)通信，可以節(jié)約大量的能量。但過多的跳數(shù)會(huì)增加信息接收轉(zhuǎn)發(fā)的次數(shù)，同樣會(huì)帶來額外的能耗。因此，將上述2個(gè)矛盾的因素折衷，適當(dāng)控制轉(zhuǎn)發(fā)節(jié)點(diǎn)的個(gè)數(shù)是降低能耗的關(guān)鍵。
   
    通常，理想狀態(tài)下具有節(jié)點(diǎn)連通性優(yōu)化作用的密度控制所要解決的核心問題同覆蓋優(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ǎ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)的位置信息�；�站采用文獻(xiàn)[11,12]中的beacons信號在網(wǎng)絡(luò)觸發(fā)階段發(fā)現(xiàn)活動(dòng)節(jié)點(diǎn)，基站負(fù)責(zé)組織協(xié)調(diào)傳感器節(jié)點(diǎn)采集相關(guān)監(jiān)測數(shù)據(jù)，匯聚融合原始傳感數(shù)據(jù)并與外界控制中心進(jìn)行聯(lián)系，最后由控制中心把處理完的有用信息傳遞給用戶。
   
    在系統(tǒng)模型中，設(shè)傳感器節(jié)點(diǎn)能夠向基站報(bào)告其剩余能量信息，并能智能地切換開啟和休眠狀態(tài)，且傳感電路和數(shù)據(jù)處理電路可以智能開關(guān)，另外，節(jié)點(diǎn)傳輸距離可以通過編程進(jìn)行調(diào)節(jié)控制。值得注意的是，SenTech公司開發(fā)的聲覺通道模塊[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ǎ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ā)送和接收信息過程中單位信息所耗損的能量，其值均取為50nJ/bit；β’表示單位信息在傳送過程中由于信號保持而在單位面積（m2）耗損的能量，其值取為100pJ/bit/ m2；m表示信息位數(shù)；d表示信息傳輸距離。
   
基于以上無線傳感器網(wǎng)絡(luò)的系統(tǒng)模型，給出以下一些定義。
   
    定義1傳感器節(jié)點(diǎn)間的連通性。若在無線傳感器網(wǎng)絡(luò)部署區(qū)域內(nèi)，節(jié)點(diǎn)之間總可以某種路由方式相互傳送信息，則稱在網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)節(jié)點(diǎn)之間是連通的。定義2無線傳感器網(wǎng)絡(luò)的連通性。若在無線傳感器網(wǎng)絡(luò)部署區(qū)域內(nèi)，對于所有節(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ǎng)絡(luò)是連通的。
   
    在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的能量主要花費(fèi)在對外界信號的轉(zhuǎn)換處理和進(jìn)行數(shù)據(jù)通信的開銷方面。由于節(jié)點(diǎn)的能量是由有限的電池提供，如果在網(wǎng)絡(luò)工作時(shí)一直讓節(jié)點(diǎn)在任何情況下都處于開啟狀態(tài)則會(huì)降低節(jié)點(diǎn)的使用壽命，從而影響整個(gè)網(wǎng)絡(luò)的使用壽命。因此，如何有效地利用基站優(yōu)化組織和管理無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)對于網(wǎng)絡(luò)的優(yōu)化應(yīng)用具有重要的意義。一類面向任務(wù)的傳感器網(wǎng)絡(luò)應(yīng)用可以選擇性地開啟覆蓋區(qū)域內(nèi)的傳感器節(jié)點(diǎn)并平衡節(jié)點(diǎn)的負(fù)載，對于任務(wù)無關(guān)的節(jié)點(diǎn)使其處于休眠狀態(tài)，這樣可以節(jié)約寶貴的傳感器節(jié)點(diǎn)能量，達(dá)到延長節(jié)點(diǎn)乃至整個(gè)網(wǎng)絡(luò)壽命的目的。

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

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

  
 
   
3基于代理的不可達(dá)節(jié)點(diǎn)解決方案
    在本節(jié)，針對第2節(jié)中在無線傳感器網(wǎng)絡(luò)部署區(qū)域內(nèi)節(jié)點(diǎn)對于基站不可達(dá)的情況，例如，由于障礙物的存在或者位于基站射頻傳輸范圍之外使得一些節(jié)點(diǎn)成為基站不可達(dá)節(jié)點(diǎn)，提出了一種在基站可達(dá)的節(jié)點(diǎn)中尋找一個(gè)節(jié)點(diǎn)作為代理來解決基站與不可達(dá)節(jié)點(diǎn)之間連通性問題的方案。
   
3.1基本思想及定義
   
    首先，給出方案的基本思想以及一些定義。 不失一般性，可以假設(shè)基站至多以2跳的方式到達(dá)所有的部署節(jié)點(diǎn)，對于所有直接到達(dá)節(jié)點(diǎn)的跳數(shù)為1，其余的都簡化為2跳，并且認(rèn)為基站可達(dá)的節(jié)點(diǎn)可以作為基站轉(zhuǎn)發(fā)傳感數(shù)據(jù)的中繼節(jié)點(diǎn)。從這些中繼節(jié)點(diǎn)中選出某些節(jié)點(diǎn)作為代理，使其作為基站與不能接收基站信息的不可達(dá)節(jié)點(diǎn)之間的通信中介。我們考慮使代理節(jié)點(diǎn)和其周圍基站不可達(dá)節(jié)點(diǎn)形成組，代理節(jié)點(diǎn)作為該組的“組長”，負(fù)責(zé)在基站和基站不可達(dá)節(jié)點(diǎn)之間的通信中介。
   
    假設(shè)S為部署在監(jiān)測區(qū)域的節(jié)點(diǎn)集合，|S|=n，基站（basestation）記為B，同時(shí)又設(shè)SR和SUR分別為部署區(qū)域內(nèi)基站可達(dá)和不可達(dá)節(jié)點(diǎn)的集合，SR和SUR定義如下：
    
 
   
    值得注意的是，由于在實(shí)際部署區(qū)域存在某些節(jié)點(diǎn)其傳輸信號不被其他任何節(jié)點(diǎn)獲悉，如掉入部署區(qū)域深坑的節(jié)點(diǎn)，集合SR∪SUR往往并不等于集合S。因此，在節(jié)點(diǎn)部署階段，使基站為每個(gè)傳感器節(jié)點(diǎn)建立以下屬性參數(shù)。
   
Blink：節(jié)點(diǎn)與基站連接狀態(tài)，取值為0或1，而分屬SR和SUR集合；
   
Nlist：集合SR中節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)；
   
Hlist：在基站信息傳輸范圍之內(nèi)節(jié)點(diǎn)的跳數(shù)表。
   
Glist：節(jié)點(diǎn)成組的成員參數(shù)。
   
3.2基于節(jié)點(diǎn)代理的方案
   
    在方案中，使得選取的代理節(jié)點(diǎn)和不可達(dá)節(jié)點(diǎn)形成相應(yīng)的組的目的是通過代理使該組中不可達(dá)節(jié)點(diǎn)可以與基站連通，因此，方案主要是在集合SR中設(shè)計(jì)一到多個(gè)代理節(jié)點(diǎn)，負(fù)責(zé)轉(zhuǎn)發(fā)基站信息到集合SUR中的相關(guān)節(jié)點(diǎn)，同時(shí)，負(fù)責(zé)作為SUR中的相關(guān)節(jié)點(diǎn)的采集信息發(fā)送到基站的中轉(zhuǎn)站。
   
    在設(shè)計(jì)代理和不可達(dá)節(jié)點(diǎn)的組時(shí)，追求一種平衡代理負(fù)載的算法以延長代理節(jié)點(diǎn)的壽命，在算法中，基站為每個(gè)節(jié)點(diǎn)增加一個(gè)屬性參數(shù)，稱為Aid，在集合SUR中用以標(biāo)識(shí)節(jié)點(diǎn)被分配給哪個(gè)代理節(jié)點(diǎn)，而其他屬于集合SR中的節(jié)點(diǎn)的Aid=0，另外，基站為集合SR的每個(gè)候選代理節(jié)點(diǎn)設(shè)置一屬性參數(shù)Glist用以識(shí)別其組成員。組的形成過程描述如下。
   
1）對于每個(gè)節(jié)點(diǎn)   
 ,基站計(jì)算其與集合SR中相鄰節(jié)點(diǎn)的Hlist值，并對獲得的節(jié)點(diǎn)Hlist值按照升序排列；
   
2）對于1）中節(jié)點(diǎn)Hlist排序結(jié)果由低到高（順序），在集合SR中依次為SUR中節(jié)點(diǎn)分配一個(gè)代理節(jié)點(diǎn)，此時(shí)存在2種情況，處理如下：
    if|Hlist（sj）|=1
   
標(biāo)記Aid（sj）=si,分配sj到惟一連通的節(jié)點(diǎn)si;加sj到Glist（si）中
    else if | Hlist（sj）|>1
   
    為sj計(jì)算分配到SR中的多個(gè)連通節(jié)點(diǎn)的成本Acost標(biāo)記Aid （sj）=sk,當(dāng)sj分配到集合SR中節(jié)點(diǎn)sk時(shí)Acost最小;加sj到Glist（sk）中在方案中，對于節(jié)點(diǎn)，如果在集合SR中存在多個(gè)節(jié)點(diǎn)與其連通，將會(huì)選擇與節(jié)點(diǎn)sj具有最小通信代價(jià)（此時(shí)為sj分配到集合SR中節(jié)點(diǎn)sk的通信成本Acost）的節(jié)點(diǎn)作為其代理，衡量Acost的2個(gè)重要因素是監(jiān)測區(qū)域內(nèi)的組成員和“組長”即代理節(jié)點(diǎn)。一種理想的情況是對于SUR中的節(jié)點(diǎn)sj，當(dāng)其分配到一個(gè)組中時(shí)，該組的代理節(jié)點(diǎn)應(yīng)滿足在所有的Hlist（sj）中是最小的，即離sj最近的節(jié)點(diǎn)，這樣節(jié)點(diǎn)間的通信能量耗費(fèi)最小。另一方面，希望在所有的代理節(jié)點(diǎn)之間實(shí)現(xiàn)負(fù)載均衡以延長網(wǎng)絡(luò)使用壽命，在傳感器網(wǎng)絡(luò)中，首個(gè)節(jié)點(diǎn)“死亡”時(shí)間是衡量網(wǎng)絡(luò)性能的重要尺度[16,17]。定義節(jié)點(diǎn)sj分配到以節(jié)點(diǎn)sk為代理的相應(yīng)組的代價(jià)為
   
Acost（k）=r1×（sj到通信成本）+r2×|（Glist（sk）|
  
    其中，sj到si通信成本的計(jì)算基于節(jié)點(diǎn)sj和si的距離，r1+r2=1，參數(shù)r1和r2是動(dòng)態(tài)可調(diào)節(jié)的量，取值與Acost（k）中sj到si通信成本和|（Glist（sk）|在節(jié)點(diǎn)成組過程中所占的比重成正比。
   
4無線傳感器網(wǎng)絡(luò)覆蓋連通性判定算法
   
    正確獲悉覆蓋在部署區(qū)域內(nèi)節(jié)點(diǎn)的連通性相關(guān)信息對網(wǎng)絡(luò)決策、管理、研究與應(yīng)用具有重要的基礎(chǔ)性作用，針對上面建立的一般意義上的無線傳感器網(wǎng)絡(luò)的系統(tǒng)模型，考慮到現(xiàn)實(shí)意義上的基站和智能節(jié)點(diǎn)可以存儲(chǔ)相關(guān)的節(jié)點(diǎn)間路由信息，如基站可以獲悉其他傳感器節(jié)點(diǎn)的能量剩余信息，可以發(fā)送相關(guān)的控制信息與參數(shù)到相應(yīng)節(jié)點(diǎn)，節(jié)點(diǎn)可以存儲(chǔ)、轉(zhuǎn)發(fā)網(wǎng)絡(luò)信息并存儲(chǔ)相關(guān)的節(jié)點(diǎn)間路由信息�；�于此，提出了在無線傳感器網(wǎng)絡(luò)應(yīng)用之前根據(jù)節(jié)點(diǎn)存儲(chǔ)的相關(guān)參數(shù)信息和路由信息進(jìn)行網(wǎng)絡(luò)節(jié)點(diǎn)連通性判定的算法。
   
    算法中使用結(jié)構(gòu)類型定義節(jié)點(diǎn)，具體如下：
    節(jié)點(diǎn)結(jié)構(gòu)定義
    StructNODE{
    NodetypeN;//節(jié)點(diǎn)類型，區(qū)分基站和普通節(jié)點(diǎn)
    floatE;//節(jié)點(diǎn)能量值
    boolv;//節(jié)點(diǎn)訪問標(biāo)志
    NODE*n[];//指向下一跳節(jié)點(diǎn)的指針集
    }
   
    算法為基于深度探測的網(wǎng)絡(luò)覆蓋連通性判定算法DBDAFNCJ（depthbaseddetectionalgorithm for network connectivity judgment），下面具體介紹。

    無線傳感器網(wǎng)絡(luò)一般都是隨機(jī)部署在監(jiān)測區(qū)域內(nèi)，一旦傳感器節(jié)點(diǎn)分布完畢，網(wǎng)絡(luò)管理者和用戶基本上就很難對節(jié)點(diǎn)進(jìn)行直接管理。此時(shí)，往往通過智能基站對具有信息存儲(chǔ)和有限計(jì)算能力和能量的節(jié)點(diǎn)進(jìn)行全局管理。因此，正確獲悉部署區(qū)域內(nèi)傳感器節(jié)點(diǎn)的工作情況是高效、合理地對網(wǎng)絡(luò)進(jìn)行管理和應(yīng)用的重要前提。首先，使用節(jié)點(diǎn)代理方案對監(jiān)測區(qū)域內(nèi)的節(jié)點(diǎn)進(jìn)行處理，設(shè)處理結(jié)果產(chǎn)生n-1個(gè)代理，這樣整個(gè)部署區(qū)域就被劃分成n個(gè)組（包括基站），DBDAFNCJ算法分別對n個(gè)組進(jìn)行處理，處理每個(gè)組時(shí)都是以基站或代理節(jié)點(diǎn)（注：統(tǒng)稱為組長節(jié)點(diǎn)）為起點(diǎn)，然后獲取相關(guān)存儲(chǔ)信息按照逐跳路由的方式對某一方向的節(jié)點(diǎn)進(jìn)行探測，算法中設(shè)置一空集，每次將探測到的節(jié)點(diǎn)加入空集，直到碰到不可達(dá)情況的節(jié)點(diǎn)，此時(shí)回溯到上一個(gè)節(jié)點(diǎn)繼續(xù)探測未被訪問的可達(dá)節(jié)點(diǎn)，當(dāng)n個(gè)組都處理完畢以后，每組節(jié)點(diǎn)的并集即是部署區(qū)域內(nèi)可以正常工作的節(jié)點(diǎn)。圖3描述了使用DBDAFNCJ算法探測各組內(nèi)節(jié)點(diǎn)連通性的方法。
   

    算法DBDAFNCJ
    AlgorithmDBDAFNCJ（）
    Begin
    Si=f
    //設(shè)置組內(nèi)連通的節(jié)點(diǎn)初始集Si為空
    Si←grouphead
    If（Gi≠f）
    //判斷與組長連通的相鄰節(jié)點(diǎn)初始集Gi為是否非空
    {Si←在Gi集中任選一個(gè)節(jié)點(diǎn)記為k并標(biāo)志為已訪問；
    Repeat{if（ki≠f）&&存在未被訪問的節(jié)點(diǎn)
    //判斷與k節(jié)點(diǎn)連通的相鄰節(jié)點(diǎn)初始集ki存在未被訪問的節(jié)點(diǎn)
    {Si←在ki集中任選一個(gè)未被訪問過的節(jié)點(diǎn)j,并標(biāo)志為已訪問；
    ki=ji;}
    ji為與j節(jié)點(diǎn)連通的相鄰節(jié)點(diǎn)集
    Else
    {回溯到上一個(gè)節(jié)點(diǎn)t
    ki=ti;
    }
    Endif;
    }
    Until 整個(gè)節(jié)點(diǎn)集合的連通子集都處理完畢
    }
    Endif
    End
   
    DBDAFNCJ算法最后輸出的結(jié)果是在網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)連通的傳感器節(jié)點(diǎn)集，由上述算法可知，DBDAFNCJ算法的時(shí)間復(fù)雜度為О（H）；空間復(fù)雜度為О（N）。其中H為算法探測的節(jié)點(diǎn)間路徑數(shù)，N為覆蓋區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)。
   
    提出的DBDAFNCJ算法具有的優(yōu)點(diǎn)為：充分利用了基站對傳感器節(jié)點(diǎn)的所存儲(chǔ)的記憶信息和節(jié)點(diǎn)間相關(guān)路由信息，為部署區(qū)域內(nèi)無線傳感器網(wǎng)絡(luò)后續(xù)研究和使用提供了有效的決策信息；算法的時(shí)間和空間復(fù)雜度比較低，易于實(shí)現(xiàn)。
   
5仿真實(shí)
   
    通過仿真實(shí)驗(yàn)對提出的節(jié)點(diǎn)代理方案和DBDAFNCJ算法進(jìn)行性能評估，下面依次給出實(shí)驗(yàn)方法、環(huán)境和結(jié)果。
   
5.1實(shí)驗(yàn)環(huán)境
   
    在廣泛使用的網(wǎng)絡(luò)仿真器ns-2的環(huán)境下用C++和TCL實(shí)現(xiàn)了節(jié)點(diǎn)代理方案和DBDAFNCJ算法,實(shí)驗(yàn)設(shè)備是一臺(tái)運(yùn)行RedhatLinux9.0,具有P42.8GHz處理器,512MB DDR內(nèi)存的PC.實(shí)驗(yàn)中，假設(shè)傳感器節(jié)點(diǎn)隨機(jī)部署在1 000m×1 000m監(jiān)測區(qū)域內(nèi)，基站被隨機(jī)地部署在監(jiān)測區(qū)域的邊界內(nèi)部，基站的傳輸半徑設(shè)為500m,節(jié)點(diǎn)的傳輸半徑設(shè)為50m，成組節(jié)點(diǎn)分配代價(jià)Acost中的a1和a2的取值各設(shè)定為0.4和0.6，主要考慮到在仿真中由于節(jié)點(diǎn)代理方案中節(jié)點(diǎn)成組代價(jià)比例稍重一些。為模擬第3節(jié)討論的實(shí)際部署區(qū)域中節(jié)點(diǎn)處于基站傳輸范圍之外和存在諸如建筑物等障礙物使得節(jié)點(diǎn)處于孤立狀態(tài)，在各種節(jié)點(diǎn)規(guī)模的仿真中，設(shè)置某一百分比的節(jié)點(diǎn)隨機(jī)部署在基站的傳輸半徑之外，在算法DBDAFNCJ的實(shí)現(xiàn)中，為簡化起見，且不影響仿真結(jié)果的可靠性，除基站外，其余節(jié)點(diǎn)均只存儲(chǔ)與其只有1跳路由關(guān)系的相鄰節(jié)點(diǎn)，為了快速得到實(shí)驗(yàn)結(jié)果并且不影響仿真結(jié)果的可靠性，把節(jié)點(diǎn)的初始能量設(shè)置為20J，采用模型中節(jié)點(diǎn)能量消耗模型，此時(shí)能量足以滿足實(shí)驗(yàn)條件，選擇一個(gè)簡化了的定向擴(kuò)散協(xié)議[18]作為網(wǎng)絡(luò)層的路由協(xié)議，修改協(xié)議使節(jié)點(diǎn)間以逐跳的方式進(jìn)行路由。
   
5.2實(shí)驗(yàn)設(shè)計(jì)及結(jié)果
   
    仿真實(shí)驗(yàn)中，主要考慮部署區(qū)域內(nèi)節(jié)點(diǎn)可達(dá)率NRR（nodereachabilityratio）作為測試指標(biāo)，計(jì)算如下：NRR=部署區(qū)域內(nèi)可達(dá)節(jié)點(diǎn)的數(shù)目/部署區(qū)域內(nèi)節(jié)點(diǎn)總數(shù).
   
    在上述仿真實(shí)驗(yàn)環(huán)境下，設(shè)計(jì)了兩類實(shí)驗(yàn)方案對節(jié)點(diǎn)代理方案和DBDAFNCJ算法進(jìn)行評估。
   
1）在部署區(qū)域內(nèi)，改變部署節(jié)點(diǎn)的數(shù)量，固定處于基站傳輸范圍之外的節(jié)點(diǎn)為總節(jié)點(diǎn)20%，把節(jié)點(diǎn)數(shù)目分為100、150、200、250、300、350、400 7種情況進(jìn)行仿真。
   
2）在部署區(qū)域內(nèi)，固定部署節(jié)點(diǎn)的數(shù)量為300，變化部署處于基站傳輸范圍之外的節(jié)點(diǎn)百分比，把百分比分為5%、10%、15%、20%、25%、30% 6種情況進(jìn)行仿真。
   
    針對兩類實(shí)驗(yàn)方案，使用DBDAFNCJ算法分別對使用節(jié)點(diǎn)代理方案部署區(qū)域節(jié)點(diǎn)預(yù)處理前后的節(jié)點(diǎn)連通性進(jìn)行判定，分別記為PRE_DBDAFNCJ和POST_DBDAFNCJ，下面給出實(shí)驗(yàn)結(jié)果。方案1）、2）的實(shí)驗(yàn)結(jié)果分別如圖4、圖5所示。

   
5.3結(jié)果分析
   
    從圖4和圖5的結(jié)果可以看出，一方面，DBDAFNCJ算法對于初始部署區(qū)域節(jié)點(diǎn)的連通性比例的判定基本與設(shè)定的節(jié)點(diǎn)連通性比例一致，說明了DBDAFNCJ算法可以很好地對部署區(qū)域內(nèi)節(jié)點(diǎn)的連通性實(shí)際情況進(jìn)行判定。另一方面，對于用節(jié)點(diǎn)代理方案處理后的部署區(qū)域使用DBDAFNCJ算法進(jìn)行節(jié)點(diǎn)連通性判定的結(jié)果表明，節(jié)點(diǎn)代理方案較好地改善了部署區(qū)域內(nèi)節(jié)點(diǎn)的連通性情況，方案1）中12%~15%的不可達(dá)節(jié)點(diǎn)實(shí)現(xiàn)了與基站的間接連通；方案2）中3%~12%的不可達(dá)節(jié)點(diǎn)實(shí)現(xiàn)了與基站的間接連通。那些最終還處于不可達(dá)狀態(tài)的節(jié)點(diǎn)是因?yàn)槠?跳范圍內(nèi)沒有基站直接可達(dá)節(jié)點(diǎn)。在現(xiàn)實(shí)情況下，如部署區(qū)域中掉入深坑的節(jié)點(diǎn)、部署完畢即出故障的節(jié)點(diǎn)均可認(rèn)為是此種情況。