引言

無線傳感器網絡（Wireless Sensor Networks，WSN）是由一組微型傳感器節點以自組織方式構成的無線網絡，其目的是協作地感知、采集和處理網絡覆蓋的地理區域中感知對象的信息，并發布給觀察者。近年來，隨著通信技術、嵌入式計算技術和傳感器技術的飛速發展和日益成熟，傳感器網絡的應用越來越廣泛。在無線傳感器網絡中，除了少數節點需要移動以外，大部分節點都是靜止的。它們通常運行在人無法接近的惡劣甚至危險的遠程環境中，能源補充非常困難，因此，設計有效的協議和算法以延長網絡的生命周期是WSN的核心問題之一。

1 相關研究

針對無線傳感器網絡能量受限的特點，對適應其特點的低功耗算法研究也一直繼續著。Heinzelman提出了LEACH（Low—Energy Adaptive Clustering Hierarchy，低能耗自適應分簇層次）算法。其核心思想是讓每個節點輪流擔當簇首，從而使得網絡中的能量消耗盡可能均勻，減少網絡失效時刻的能量浪費。LEACH算法只考慮了單跳模型，因此只適合于小型wSN網絡。參考文獻提出了M—LEACH（Multi—hop variant of LEACH，多跳LEACH）算法，簇內的節點不是以單跳的方式傳輸數據到簇首，而是通過簇內其他節點轉發。參考文獻提出了一個多跳簇首模型，采用從下到上的策略，逐層生成每一層的簇首，最終得到一個多層結構的WSN網絡。參考文獻采用基于代價的目標函數對傳感器網絡設計進行了分析，推導出單跳和多跳的適用范圍，最后提出一種單跳多跳混合的路由算法，以解決網絡中的“能量熱點”問題。本文在前人研究的基礎上提出一種適合無線傳感器網絡能量受限特點的低功耗路由算法。

2 網絡模型

無線傳感器網絡是由大量部署在觀測環境中的微型、廉價、低功耗的傳感器節點，以無線、自組織的方式，通過多跳通信而快速形成的網絡系統。WSN的典型布撒是通過飛行器撒播、人工埋置和火箭彈射等方式來完成的。圖1給出了傳感器網絡體系結構一般形式的描述。

假定傳感器網絡中的各節點隨機均勻分布在一個方形區域內，并且具有如下性質：

①惟一的基站部署在網絡外部較遠的位置；

②每個節點有惟一的標識；

③傳感器節點部署后不再移動；

④所有節點平等，具有相同的計算和通信能力；

⑤節點的地理位置信息不可知；

⑥發射節點與不同距離的接收節點通信時，可以調整發射功率。

3 算法描述

本算法采用LEACH算法中“輪”的思想，每一輪工作由2個階段組成：一是簇的建立階段；二是數據傳輸階段。在簇的建立階段，主要完成簇首的選取、簇的生成，以及時限的分配；在數據傳輸階段，主要完成的是各個傳感器節點把采集到的數據逐層上傳到基站，其中包括必要的數據融合、數據加密等處理。

3．1 簇的結構及首輪簇首選舉

在無線傳感器網絡分簇算法的研究中，大部分都是在網絡簇的同構模型上進行研究，例如如何使各個簇的節點數目盡量相同、簇的大小盡量相同，在此基礎上有效地降低能量的消耗。多數的分簇算法都采用簇首多跳將數據傳輸到基站，使得距離基站較近的節點不但要收集本簇內節點傳送上來的數據，而且同時要轉發其他比它距離基站遠的簇首節點發送的數據，這就使得距離基站較近的節點要比遠離基站的簇首節點消耗更多的能量。如果采用簇結構同構的分簇方法，往往距離基站較近的簇首能量消耗要相對大，導致新一輪的簇首選舉，造成整個網絡暫停工作，甚至于節點早期進入死亡階段。為了避免這種情況發生，本算法初步采用簇大小異構的方法，即距離基站遠的簇結構比距離基站近的簇結構大，來均衡轉發數據的能量消耗。

在網絡部署階段，基站用一個給定的發送功率向網絡內廣播一個信號。每個傳感器節點在接收到此信號后，根據接收信號的強度計算它到基站的近似距離。獲得這個距離，不僅有助于傳感器節點向基站傳輸數據時選擇合適的發送功率以降低能量消耗，而且它還是算法構造大小非均勻的簇的必需信息之一。非均勻分簇網絡結構如圖2所示。

靠近基站的候選簇首的競爭半徑應該較小。隨著候選簇首到基站距離的減小，其競爭半徑亦應隨之減小。設候選簇首的競爭半徑的最大取值為R0c。其中，c用于控制取值范圍的參數，在0～1之間取值。候選簇首si確定其競爭半徑Rc的計算公式如下：

式中：dmax是距離基站最大的距離；dmin是距離基站最小的距離；d（si，DS）是簇首si到基站DS的距離。

首輪簇首選舉相對簡單。根據簇首節點比例在網絡中選舉出簇首，在競爭半徑內不允許存在其他簇首，接著競選產生的簇首向全網廣播其競選獲勝的消息 CH_ADV_MSG；普通節點選擇簇內通信代價最小（即接收信號強度最大）的簇首，發送加入消息JOIN_CLUSTER_MSG通知該簇首。

3．2 簇首生成樹的建立及數據傳輸

本文采用簇首多跳數據傳輸的方法，如何選舉下一跳簇首節點是本部分要重點闡述的問題。首先引入一個閾值TD_MAX，若簇首到匯聚點的距離小于TD_MAX，則直接與匯聚點進行通信；否則，應該盡量使用多跳路由的方式將數據傳送給匯聚點。

假設d（A，DS）》TD_MAX，則在簇首A的臨近簇首集里計算各個若簇首，帶來的鏈路質量開銷指標 Erelay=d2（A，X）+d2（X，DS）。其中，d（A，X）是簇首A到簇首X的距離；d（X，DS）是簇首X到基站距離；d（A，DS）是簇首 A到基站的距離。在Erelay值小的簇首節點中選擇剩余能量最大的節點作為中繼轉發的簇首節點，將數據按照簇首生成樹轉發到基站。

3．3 各輪簇首選舉

為了延長網絡的生命周期，應該盡量選擇簇內節點中剩余能量最高的節點為簇首節點，并且讓不同的節點輪轉當選。本部分采用基于剩余能量的簇首簇內輪換的方法進行簇首選舉。其主要思想：簇首在簇內負責收集簇內節點的數據。在節點向簇首發送數據時，在數據位后附加上本節點的剩余能量值位。簇首將數據進行處理轉發后，對各節點的能量進行簡單的排序，因為不用維持所有節點能量的全排序，只需要知道剩余能量比較高的幾個節點，所以采用最大堆的排序方法。在通過數據應答包或者命令包中附加位的方法把這個排序中的前3名節點號及能量值廣播到整個簇內，這樣做就不會增加廣播次數，只是以附帶的方式就可以使整個簇內節點都有本簇內剩余能量較高節點的信息。即使簇首節點突然失效或發生異常，其他的節點可以很快根據能量信息選出新簇首。簇內節點保留的都是最近一次的能量信息，由于傳感器網絡休眠的時同比較長，即使簇首突然失效，信息的變化也不會很大，完全可以根據這次排序來選舉出新的簇首。新簇首選出后，負責完成數據收發處理及能量排序等工作。

通過本算法每次都選出剩余能量最多的節點當選簇首，使簇內信息收集和主干網絡通信更加穩定，并避免了每輪簇首選舉時所有節點相互交換能量信息所需的大量開銷。

4 性能分析

本部分比較各種分簇協議對網絡存活時間的影響。圖3顯示了網絡中存活節點數目的各輪變化情況。從圖中可以看出，無論是第一個節點死亡的時間還是最后一個節點死亡的時間，本文算法均優于其他3種協議。節點死亡時間的跨度可以反映出網絡中節點的能量均衡情況，時間跨度短說明網絡的能量使用高效。本文算法不僅顯著地延長了網絡的生存時間，而且時間跨度也小于其他3種協議，這說明該算法很好地均衡了網絡中所有節點的能量消耗。

通過試驗結果可以看出，本文提出的算法具有如下優點：分簇算法穩定，所生成簇的簇個數不變，能量消耗低，且有效平衡了簇首能量消耗，顯著延長路網絡的生存時間。總之，用網絡的生存時間這一重要指標來衡量，其性能顯著優于其他3種分簇協議。

5 總結

本文算法在初始化簇結構時，采用非均勻分簇的方法，避免了由于數據沿簇首生成樹多跳傳輸而導致近基站簇首多余能量的消耗，解決了簇首能量不均衡的問題；采用基于剩余能量的簇首簇內選舉的方法，避免了所有節點參與每輪的簇首選舉過程帶來的不必要的能量消耗，保證了剩余能量最多的節點擔任下一任簇首；用簇首建立主干網絡進行數據多跳傳輸，合理選擇下一跳簇首節點，減少了簇頭長距離傳輸數據的能量消耗。

責任編輯：gt