作 者：黃曉 程宏兵 楊庚

    摘要：針對無線傳感器網絡部署區域由于通信障礙和其他一些因素產生的某些節點無法與網絡通信的情況，給出了一種使用節點代理解決監測區域內節點通信不可達的方案，并基于一般意義的網絡系統模型提出了一種探測覆蓋區域內節點連通性的算法，即基于深度探測的節點覆蓋連通性判定算法DBDAFNCJ。節點連通性分析和仿真實驗結果表明，節點代理方案可以很好改善節點部署區域內節點通信不可達的情況，同時表明DBDAFNCJ算法可以高效、準確地獲悉部署區域內節點連通性的情況。

    1引言

    集成傳感器技術、微機電系統（MEMS）技術、無線通信技術和分布式信息處理技術的無線傳感器網絡（WSN,wirelesssensornetworks）是當前信息技術的前沿之一，也是當今的研究熱點，受到了廣泛的關注。目前，無線傳感器網絡逐漸成為一種廉價、方便的信息采集方法，尤其是在敵對和惡劣的網絡應用環境下，傳統的方法代價高昂而幾乎無法使用。如文獻[1~3]中的戰場生存性應用、一些安全相關的應用以及災難管理等應用，無線傳感器網絡都顯示了巨大的應用價值。在上述應用中，傳感器節點往往是隨機地部署在監測區域，一直工作到能量耗盡為止。

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

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

    針對傳感器網絡的覆蓋連通性問題，本文將在第2節討論無線傳感器網絡覆蓋連通性理論及網絡模型。第3節采用了一種節點代理基站來解決網絡中不可達節點的連通性方案。第4節將給出在第2節中所給模型的基礎上進行網絡覆蓋連通性判定的算法。第5節對提出的基站代理方案和節點連通性判定算法進行實驗。第6節是結束語。

    2網絡覆蓋連通性理論及網絡模型

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

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

    基于上述理論，給出一個一般意義上的無線傳感器網絡模型，描述如下。

    設N個傳感器節點隨機地部署在某一區域，節點擁有有限的電池能量和數據處理能力，在網絡應用中節點的任務是按照外界控制中心的需要進行動態的工作，基站部署在其他傳感器節點附近。假設傳感器節點和基站都處于靜止狀態，且基站可以獲悉其他節點的位置信息。基站采用文獻[11,12]中的beacons信號在網絡觸發階段發現活動節點，基站負責組織協調傳感器節點采集相關監測數據，匯聚融合原始傳感數據并與外界控制中心進行聯系，最后由控制中心把處理完的有用信息傳遞給用戶。

    在系統模型中，設傳感器節點能夠向基站報告其剩余能量信息，并能智能地切換開啟和休眠狀態，且傳感電路和數據處理電路可以智能開關，另外，節點傳輸距離可以通過編程進行調節控制。值得注意的是，SenTech公司開發的聲覺通道模塊[13]傳感器節點具有上述功能。設傳感器節點可以作為數據轉發的中繼。基站擁有可以根據實際任務和環境的需要智能地選取部分傳感器節點進行工作、選擇數據路由以及媒體訪問仲裁的網絡管理功能。在網絡系統模型中，網絡的組織和管理都是基于能量意識的，依賴于每個傳感器節點的能量知識，網絡的控制參照傳感器節點的工作狀況和能量剩余情況。

    在系統中，參考文獻[14,15]中節點通信時的能量消耗模型，模型中定義的節點發送信息和接受信息的能量消耗公式如下。

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

    基于以上無線傳感器網絡的系統模型，給出以下一些定義。

    定義1傳感器節點間的連通性。若在無線傳感器網絡部署區域內，節點之間總可以某種路由方式相互傳送信息，則稱在網絡覆蓋區域內節點之間是連通的。

    定義2無線傳感器網絡的連通性。若在無線傳感器網絡部署區域內，對于所有節點的極大子集，基站總是可以某種路由方式傳送相關控制信息到該節點集合中的任何節點，且該節點集合中的任意節點間也是連通的，則稱在該網絡覆蓋區域內由此極大節點子集組成的無線傳感器網絡是連通的。

    在無線傳感器網絡中，傳感器節點的能量主要花費在對外界信號的轉換處理和進行數據通信的開銷方面。由于節點的能量是由有限的電池提供，如果在網絡工作時一直讓節點在任何情況下都處于開啟狀態則會降低節點的使用壽命，從而影響整個網絡的使用壽命。因此，如何有效地利用基站優化組織和管理無線傳感器網絡節點對于網絡的優化應用具有重要的意義。一類面向任務的傳感器網絡應用可以選擇性地開啟覆蓋區域內的傳感器節點并平衡節點的負載，對于任務無關的節點使其處于休眠狀態，這樣可以節約寶貴的傳感器節點能量，達到延長節點乃至整個網絡壽命的目的。

上述網絡優化過程的前提是基站必須獲悉網絡中節點情況，只有確保覆蓋區域內網絡節點的連通性基站才能有效地對節點進行組織和管理。在傳感器網絡通信中，節點與基站之間理想通信模式是使用短距離的通信方式，這種方式假設基站對于網絡中的節點在任何情況下都是可達的，然而，這并不符合實際。因為在部署傳感器網絡時沒有統一的模式，且網絡部署環境有很大差別。在許多實際應用場景中存在各種障礙物（如建筑物、樹木以及其他一些干擾信號等）會阻礙節點和基站之間的正常通信，有時這些障礙物甚至會使節點處于不可用狀態。

    圖1描述的是當基站和傳感器節點都處于彼此的通信范圍內時，由于障礙物的存在使得基站不能夠與被阻礙節點進行直接通信的情況。

    對于基站和傳感器節點不能直接通信的另一種情況如圖2所示，在傳感器網絡部署區域內，有部分節點處于基站的傳輸范圍之外，此時基站和這部分節點就不能進行直接通信。

    3基于代理的不可達節點解決方案

    在本節，針對第2節中在無線傳感器網絡部署區域內節點對于基站不可達的情況，例如，由于障礙物的存在或者位于基站射頻傳輸范圍之外使得一些節點成為基站不可達節點，提出了一種在基站可達的節點中尋找一個節點作為代理來解決基站與不可達節點之間連通性問題的方案。

    3.1基本思想及定義

    首先，給出方案的基本思想以及一些定義。

    不失一般性，可以假設基站至多以2跳的方式

    到達所有的部署節點，對于所有直接到達節點的跳數為1，其余的都簡化為2跳，并且認為基站可達的節點可以作為基站轉發傳感數據的中繼節點。從這些中繼節點中選出某些節點作為代理，使其作為基站與不能接收基站信息的不可達節點之間的通信中介。我們考慮使代理節點和其周圍基站不可達節點形成組，代理節點作為該組的“組長”，負責在基站和基站不可達節點之間的通信中介。

    假設S為部署在監測區域的節點集合，|S|=n，基站（basestation）記為B，同時又設SR和SUR分別為部署區域內基站可達和不可達節點的集合，SR和SUR定義如下：

    值得注意的是，由于在實際部署區域存在某些節點其傳輸信號不被其他任何節點獲悉，如掉入部署區域深坑的節點，集合SR∪SUR往往并不等于集合S。因此，在節點部署階段，使基站為每個傳感器節點建立以下屬性參數。

    Blink：節點與基站連接狀態，取值為0或1，而分屬SR和SUR集合；

    Nlist：集合SR中節點的所有鄰居節點；

    Hlist：在基站信息傳輸范圍之內節點的跳數表。

    Glist：節點成組的成員參數。

   3.2基于節點代理的方案

    在方案中，使得選取的代理節點和不可達節點形成相應的組的目的是通過代理使該組中不可達節點可以與基站連通，因此，方案主要是在集合SR中設計一到多個代理節點，負責轉發基站信息到集合SUR中的相關節點，同時，負責作為SUR中的相關節點的采集信息發送到基站的中轉站。

    在設計代理和不可達節點的組時，追求一種平衡代理負載的算法以延長代理節點的壽命，在算法中，基站為每個節點增加一個屬性參數，稱為Aid，在集合SUR中用以標識節點被分配給哪個代理節點，而其他屬于集合SR中的節點的Aid=0，另外，基站為集合SR的每個候選代理節點設置一屬性參數Glist用以識別其組成員。組的形成過程描述如下。

    1)對于每個節點,基站計算其與集合SR中相鄰節點的Hlist值，并對獲得的節點Hlist值按照升序排列；

    2)對于1)中節點Hlist排序結果由低到高（順序），在集合SR中依次為SUR中節點分配一個代理節點，此時存在2種情況，處理如下：

    if|Hlist(sj)|=1

    標記Aid(sj)=si,分配sj到惟一連通的節點si;加sj到Glist(si)中

    else if | Hlist(sj)|>1

    為sj計算分配到SR中的多個連通節點的成本Acost

    標記Aid (sj)=sk,當sj分配到集合SR中節點sk時Acost最小;加sj到Glist(sk)中

    在方案中，對于節點，如果在集合SR中存在多個節點與其連通，將會選擇與節點sj具有最小通信代價（此時為sj分配到集合SR中節點sk的通信成本Acost）的節點作為其代理，衡量Acost的2個重要因素是監測區域內的組成員和“組長”即代理節點。一種理想的情況是對于SUR中的節點sj，當其分配到一個組中時，該組的代理節點應滿足在所有的Hlist(sj)中是最小的，即離sj最近的節點，這樣節點間的通信能量耗費最小。另一方面，希望在所有的代理節點之間實現負載均衡以延長網絡使用壽命，在傳感器網絡中，首個節點“死亡”時間是衡量網絡性能的重要尺度[16,17]。定義節點sj分配到以節點sk為代理的相應組的代價為

    Acost(k)=r1×(sj到通信成本)+r2×|(Glist(sk)|

    其中，sj到si通信成本的計算基于節點sj和si的距離，r1+r2=1，參數r1和r2是動態可調節的量，取值與Acost(k)中sj到si通信成本和|(Glist(sk)|在節點成組過程中所占的比重成正比。

    4無線傳感器網絡覆蓋連通性判定算法

    正確獲悉覆蓋在部署區域內節點的連通性相關信息對網絡決策、管理、研究與應用具有重要的基礎性作用，針對上面建立的一般意義上的無線傳感器網絡的系統模型，考慮到現實意義上的基站和智能節點可以存儲相關的節點間路由信息，如基站可以獲悉其他傳感器節點的能量剩余信息，可以發送相關的控制信息與參數到相應節點，節點可以存儲、轉發網絡信息并存儲相關的節點間路由信息。基于此，提出了在無線傳感器網絡應用之前根據節點存儲的相關參數信息和路由信息進行網絡節點連通性判定的算法。

    算法中使用結構類型定義節點，具體如下：

    節點結構定義

    StructNODE{

    NodetypeN;//節點類型，區分基站和普通節點

    floatE;//節點能量值

    boolv;//節點訪問標志

    NODE*n[];//指向下一跳節點的指針集

    }

    算法為基于深度探測的網絡覆蓋連通性判定算法DBDAFNCJ(depthbaseddetectionalgorithm for network connectivity judgment)，下面具體介紹。

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

    算法DBDAFNCJ

    AlgorithmDBDAFNCJ()

    Begin

    Si=f

    //設置組內連通的節點初始集Si為空

    Si←grouphead

    If(Gi≠f)

    //判斷與組長連通的相鄰節點初始集Gi為是否非空

    {Si←在Gi集中任選一個節點記為k并標志為已訪問；

    Repeat{if(ki≠f)&&存在未被訪問的節點

    //判斷與k節點連通的相鄰節點初始集ki存在未被訪問的節點

    {Si←在ki集中任選一個未被訪問過的節點j,并標志為已訪問；

    ki=ji;}

    ji為與j節點連通的相鄰節點集

    Else

    {回溯到上一個節點t

    ki=ti;

    }

    Endif;

    }

    Until 整個節點集合的連通子集都處理完畢

    }

    Endif

    End

    DBDAFNCJ算法最后輸出的結果是在網絡覆蓋區域內連通的傳感器節點集，由上述算法可知，DBDAFNCJ算法的時間復雜度為О(H)；空間復雜度為О(N)。其中H為算法探測的節點間路徑數，N為覆蓋區域內的節點數。

    提出的DBDAFNCJ算法具有的優點為：充分利用了基站對傳感器節點的所存儲的記憶信息和節點間相關路由信息，為部署區域內無線傳感器網絡后續研究和使用提供了有效的決策信息；算法的時間和空間復雜度比較低，易于實現。

    5仿真實

    通過仿真實驗對提出的節點代理方案和DBDAFNCJ算法進行性能評估，下面依次給出實驗方法、環境和結果。

    5.1實驗環境

    在廣泛使用的網絡仿真器ns-2的環境下用C++和TCL實現了節點代理方案和DBDAFNCJ算法,實驗設備是一臺運行RedhatLinux9.0,具有P42.8GHz處理器,512MB DDR內存的PC.實驗中，假設傳感器節點隨機部署在1 000m×1 000m監測區域內，基站被隨機地部署在監測區域的邊界內部，基站的傳輸半徑設為500m,節點的傳輸半徑設為50m，成組節點分配代價Acost中的a1和a2的取值各設定為0.4和0.6，主要考慮到在仿真中由于節點代理方案中節點成組代價比例稍重一些。為模擬第3節討論的實際部署區域中節點處于基站傳輸范圍之外和存在諸如建筑物等障礙物使得節點處于孤立狀態，在各種節點規模的仿真中，設置某一百分比的節點隨機部署在基站的傳輸半徑之外，在算法DBDAFNCJ的實現中，為簡化起見，且不影響仿真結果的可靠性，除基站外，其余節點均只存儲與其只有1跳路由關系的相鄰節點，為了快速得到實驗結果并且不影響仿真結果的可靠性，把節點的初始能量設置為20J，采用模型中節點能量消耗模型，此時能量足以滿足實驗條件，選擇一個簡化了的定向擴散協議[18]作為網絡層的路由協議，修改協議使節點間以逐跳的方式進行路由。

    5.2實驗設計及結果

    仿真實驗中，主要考慮部署區域內節點可達率NRR（nodereachabilityratio）作為測試指標，計算如下：

    NRR=部署區域內可達節點的數目/部署區域內節點總數

    在上述仿真實驗環境下，設計了兩類實驗方案對節點代理方案和DBDAFNCJ算法進行評估。

    1)在部署區域內，改變部署節點的數量，固定處于基站傳輸范圍之外的節點為總節點20%，把節點數目分為100、150、200、250、300、350、400 7種情況進行仿真。

    2)在部署區域內，固定部署節點的數量為300，變化部署處于基站傳輸范圍之外的節點百分比，把百分比分為5%、10%、15%、20%、25%、30% 6種情況進行仿真。

    針對兩類實驗方案，使用DBDAFNCJ算法分別對使用節點代理方案部署區域節點預處理前后的節點連通性進行判定，分別記為PRE_DBDAFNCJ和POST_DBDAFNCJ，下面給出實驗結果。方案1）、2）的實驗結果分別如圖4、圖5所示。

    5.3結果分析

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

    6結束語

    對于隨機部署在監測區域的無線傳感器網絡節點連通性的研究是其后續研究、管理和應用的基礎，針對在實際應用中，節點隨機部署而可能出現與基站不能正常通信的問題，提出了一種使用與基站連通的節點作為代理解決基站不可達節點的方案，并基于節點存儲的路由信息給出了一種節點連通性的判定算法，仿真實驗中，在改變仿真節點數目而固定不可達節點比例以及固定仿真節點數目而改變不可達節點比例2種情況下，結果均表明所提出的節點代理方案可以有效地改善部署區域的節點不可達問題，同時表明，所提出的節點連通性判定算法能夠高效地探測部署區域內節點的連通性狀況。