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

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

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

0 引言

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

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

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

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

然而，將RP 看成區(qū)域內位置存在優(yōu)勢。圖1描述1 個網絡示例。

圖1 RP 的選擇（示例）

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

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

1 系統(tǒng)模型

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

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

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

2 HADC 算法

2.1 基于層次聚類的簇

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

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

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

式中： si∈ cx； sj∈ cy。

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

圖3 執(zhí)行凝聚法過程

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

2.2 RP 的選擇

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

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

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

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

式中 d (CPj, Pi)為Gj簇內節(jié)點 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 )計算在每一層λ 的最優(yōu)簇數，即 kopt為

3 實驗與結果分析

3.1 仿真環(huán)境

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

表1 仿真參數

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

3.2 平均能耗

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

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

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

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

圖4 不同算法的平均能耗

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

3.3 網絡壽命

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

圖5 網絡壽命

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

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

3.4 能耗均衡

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

式中：eβ 表示傳感節(jié)點的能耗的標準差； 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 算法通過信宿的移動收集數據，進而平衡網絡內節(jié)點間的能耗。先利用層次凝聚法產生簇，并從能耗角度優(yōu)化簇個數，再將每個簇內的質心位置作為駐留點，進而產生駐留點集。這些駐留點就構建了移動信宿的移動路徑。仿真結果表明，提出的HADC 算法有效地減少了能耗，并均衡了能耗的平衡性。