WSNs 中基于凝聚法的信宿移動路徑規劃

王 梅，繆相林，張 媛，丁 凰

（1.西安交通大學 城市學院，西安 710018；2.西安交通大學 計算機學院，西安 710049）

0 引言

隨著電子通信技術的快速發展，無線傳感網絡（wireless sensor networks, WSNs）[1]已在多個領域使用，如智慧農業、海洋環境勘察等領域。WSNs是由微型的、具有感知、通信、數據處理的傳感節點組成。每個節點感測環境數據，再將數據傳輸至信宿或控制中心。最終，由信宿或控制中心對數據進行分析處理，進而實現對環境的監測。

不失一般性，這些微型傳感節點由電池供電。因此，如何提高節點能量效率，進而使節點工作的時間更長，成為WSNs 的研究熱點之一。由于節點須以多跳方式向信宿傳輸數據，傳輸數據消耗了節點的大部分能量。而位于信宿附近的節點，須多次協作轉發其他節點的數據，它們的能量消耗速度更快，這就形成熱點問題[2-3]。

熱點問題阻礙了信宿的數據收集。因此，平衡網絡內節點的能耗[4]，進而提高數據收集效率是十分有必要的。為了緩解熱點問題，采用了移動信宿[5-7]（mobile sink, MS）概念，如移動機器人、無人機（unmanned aerial vehicle, UAV）。MS 通過遍歷 WSNs 內每個節點，能夠直接收集節點數據。

然而，遍歷網絡內每個節點是非常耗時的。為了減少遍歷時間，MS 只遍歷網絡內部分點，這些點稱為駐留點（rendezvous point, RP）[8-11]。這些RP 可能是網絡內的節點或者網絡區域內位置。多數文獻是將RP 看成節點。

然而，將RP 看成區域內位置存在優勢。圖1描述1 個網絡示例。

圖1 RP 的選擇（示例）

圖1 （a）中，由于節點0、1、2、3、6 或7的覆蓋區域與其他的3 個節點重疊，它們很可能被選為RP。而若考慮位置作為RP，如圖1（b）所示，將三角形位置作為RP，則RP 能夠直接與多個節點通信。

有效地選擇RP 能夠均衡網絡能耗，控制擁塞，進而提高網絡壽命[3]。為此，本文針對3 維WSNs，提出基于層次聚類法的數據收集（hierarchical agglomerative-based data collecting, HADC）算法。先利用層次聚類將節點劃分不同簇，并利用層次聚類得到最優的簇數，再將每個簇的中心位置作為RP。MS 就沿著RP 移動，進而收集網絡內數據。

1 系統模型

n 個 節 點 隨 機 分 布 于 ? · ? ·? 立 體 區 域 內，用S= {s1, s2, s3,… , sn}表 示 這 n 個 節 點 集， 用Pi= ( xi, yi,zi)表示 si節點的位置。

用M 表示RP 集。MS 依據RP 移動，并收集數據。如圖2 所示，假定MS 在遍歷每個RP 所消耗的時間足夠用于數據的收集，信宿知曉網絡內所有節點的位置，并假定MS 有足夠的存儲空間和能量收集數據，且在MS 的移動路徑中無障礙。

圖2 基于RP 的MS 收集數據過程

2 HADC 算法

2.1 基于層次聚類的簇

層次聚類算法屬于無監督的機器學習算法，有2 種策略：自底向上的凝聚法和自上向下的分裂法。凝聚法是指許多基于相同原則構建的聚類算法；分裂法是將初始樣本歸成1 個簇，再依據具體準則逐步分裂，直至滿足預設的條件，才終止分裂。

凝聚法將初始樣本看作1 個類簇，再依據具體準則合并這些類簇，直到滿足預設的條件，才終止。HADC 算法引用凝聚法，并利用2 個簇間的最小距離作為合并的依據。

對于2 個簇 cx和 cy，它們的距離等于這2 個簇內節點間的最小距離值，即

式中： si∈ cx； sj∈ cy。

凝聚法最初并不設定所需的簇數，而是通過對簇進行迭代，直到每個節點都歸屬1 個唯一的簇。圖3 給出了執行凝聚法過程。

圖3 執行凝聚法過程

從圖3 可知：凝聚法先假定每個節點作為1 個簇，即n 個節點形成n 個簇；依據式（1）尋找相距最近的簇，并將它們合并成1 個簇；再依據式（1）迭代，直至滿足條件。這就形成基于簇的樹結構，將其稱為凝聚簇樹的層次結構。

2.2 RP 的選擇

依據算法1，可得到λ 級簇類層次拓撲結構，且 n ≥ λ≥ 1。每1 層包含k 個簇，即 Cλ= {G1, G2,… ,Gj,… , Gk}，其中Gj表示第j 個簇。且用 nj表示Gj簇內的節點數。

優化λ 值，選擇最優的RP，進而能夠提高數據收集效率，降低能耗。據此，需要采用優化算法決策λ 值。HADC 算法采用統計算法估計最優的λ 值。

具體而言，先計算每個簇的質心位置CP。令CPj表示Gj簇的質心位置，其定義為

對于單個的Gj簇，將簇內所有節點離簇質心CPj的距離的平均值作為簇的權重，即

式中 d (CPj, Pi)為Gj簇內節點 Pi∈ Gj離CPj的距離。

簇內權重（inter-cluster weight, ICW）等于簇權重的均值，即簇Gj的ICW 為

用簇間距離（intra-cluster distance, ICD）表述2 個簇間的距離，簇Gj的 ICD ( j )等于在同一層中所有簇離自己的最小距離，其定義為

引入簇的緊湊-分離率（compact-separate proportion, CSP）變量，其定義為

并計算在iλ 層的k 個簇的CSP 的平均值

依據 A_CSP ( k )計算在每一層λ 的最優簇數，即 kopt為

3 實驗與結果分析

3.1 仿真環境

通過派森（Python）軟件構建仿真平臺，分析HADC 算法的性能。在100 m × 1 00 m × 1 00 m 的區域部署 100～400 個節點。sink 的移動速度為?= 0.5m/s ，具體的仿真參數如表1 所示。

表1 仿真參數

為了更好地分析HADC 算法的性能，選擇文獻[9]提出的權重駐留點規劃（weight rendezvous planning, WRP）算法、文獻[10]提出的移動信宿的有效數據收集（efficient data gathering with mobile sink, EDGS）算法和文獻[12]提出的基于層次簇的駐留點的數據收集（hierarchical clusteringbased determine rendezvous data gathering, HCRG）算法作為參照，并分析它們的能耗、網絡壽命的性能。

3.2 平均能耗

將MS 在遍歷1 輪時，網絡內所有節點的能耗平均值作為平均能耗，其定義為

式中：n 為傳感節點數；iE 為節點is 所消耗的能量。

圖4 顯示了HADC 算法、WRP、EDGS 和HCRG 算法的平均能耗隨節點數的變化情況。

由圖4 可知，平均能耗隨節點的增加而呈上升關系。原因在于：節點數的越多，所產生的數據包數越多，節點需要轉發的數據包數也越多，這必然增加節點能耗。

圖4 不同算法的平均能耗

相比于WRP、EDGS 和HCRG 算法，本文提出的HADC 算法的平均能耗得到有效的控制。與WRP 算法相比，HADC 算法的能耗下降約46%。這要歸結于HADC 算法通過優化簇，并利用簇內質心位置作為RP 位置，進而優化了RP 集。

3.3 網絡壽命

本次實驗分析HADC 算法的網絡壽命，將MS從網絡開始至網絡內第1 個節點的能耗殆盡所遍歷的輪數作為網絡壽命。圖5 顯示了HADC 算法的網絡壽命隨節點數的變化情況。

圖5 網絡壽命

從圖5 可知，節點數的增加，降低了網絡壽命，這與圖4 的能耗數據匹配。能耗的增加，加速了節點能耗速度，使出現能耗殆盡節點的時間提前。

相比于WRP、EDGS 和HCGR 算法，HADC算法的網絡壽命得到有效提高。相比WRP、EDGS和HCGR 算法，HADC 算法的第一能量消耗殆盡節點出現的輪數分別推遲了約1 446、1 109 和1 069 輪。

3.4 能耗均衡

引用公平指標（fairness index）表征網絡節點間的能耗均衡性能，其定義為

式中：eβ 表示傳感節點的能耗的標準差； Em、uE分別表示最大的能耗和最小能耗。eβ 值越大，公平指標F 值越低。

圖6 顯示了WRP、EDGS、HCGR 算法和HADC算法的公平指標隨運行輪數的變化情況。

圖6 能耗均衡的公平指標

從圖6 可知，HADC 算法的F 值接近1。即使運行150 輪后，HADC 算法的F 值也達到0.97。相比之下WRP、EDGS、HCGR 算法的F 值隨運行輪數的增加，快速下降，當運行150 輪后，它們的F 值低至0.5。

4 結束語

針對3 維的WSN 網絡，提出基于層次聚類法的數據收集HADC 算法。HADC 算法通過信宿的移動收集數據，進而平衡網絡內節點間的能耗。先利用層次凝聚法產生簇，并從能耗角度優化簇個數，再將每個簇內的質心位置作為駐留點，進而產生駐留點集。這些駐留點就構建了移動信宿的移動路徑。仿真結果表明，提出的HADC 算法有效地減少了能耗，并均衡了能耗的平衡性。