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

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

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

0 引言

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

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

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

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

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

圖1 RP 的選擇（示例）

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

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

1 系統(tǒng)模型

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

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

圖2 基于RP 的MS 收集數(shù)據(jù)過程

2 HADC 算法

2.1 基于層次聚類的簇

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

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

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

式中： si∈ cx； sj∈ cy。

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

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

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

2.2 RP 的選擇

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

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

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

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

式中 d (CPj, Pi)為Gj簇內(nèi)節(jié)點 Pi∈ Gj離CPj的距離。

簇內(nèi)權(quán)重（inter-cluster weight, ICW）等于簇權(quán)重的均值，即簇Gj的ICW 為

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

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

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

依據(jù) A_CSP ( k )計算在每一層λ 的最優(yōu)簇數(shù)，即 kopt為

3 實驗與結(jié)果分析

3.1 仿真環(huán)境

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

表1 仿真參數(shù)

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

3.2 平均能耗

將MS 在遍歷1 輪時，網(wǎng)絡(luò)內(nèi)所有節(jié)點的能耗平均值作為平均能耗，其定義為

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

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

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

圖4 不同算法的平均能耗

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

3.3 網(wǎng)絡(luò)壽命

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

圖5 網(wǎng)絡(luò)壽命

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

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

3.4 能耗均衡

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

式中：eβ 表示傳感節(jié)點的能耗的標(biāo)準(zhǔn)差； Em、uE分別表示最大的能耗和最小能耗。eβ 值越大，公平指標(biāo)F 值越低。

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

圖6 能耗均衡的公平指標(biāo)

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

4 結(jié)束語

針對3 維的WSN 網(wǎng)絡(luò)，提出基于層次聚類法的數(shù)據(jù)收集HADC 算法。HADC 算法通過信宿的移動收集數(shù)據(jù)，進而平衡網(wǎng)絡(luò)內(nèi)節(jié)點間的能耗。先利用層次凝聚法產(chǎn)生簇，并從能耗角度優(yōu)化簇個數(shù)，再將每個簇內(nèi)的質(zhì)心位置作為駐留點，進而產(chǎn)生駐留點集。這些駐留點就構(gòu)建了移動信宿的移動路徑。仿真結(jié)果表明，提出的HADC 算法有效地減少了能耗，并均衡了能耗的平衡性。