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

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

0 引言

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

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

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

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

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

圖1 RP 的選擇（示例）

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

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

1 系統(tǒng)模型

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

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

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

2 HADC 算法

2.1 基于層次聚類的簇

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

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

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

式中： si∈ cx； sj∈ cy。

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

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

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

2.2 RP 的選擇

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

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

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

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

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

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

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

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

并計(jì)算在iλ 層的k 個(gè)簇的CSP 的平均值

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 仿真環(huán)境

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

表1 仿真參數(shù)

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

3.2 平均能耗

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

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

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

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

圖4 不同算法的平均能耗

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

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

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

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

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

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

3.4 能耗均衡

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

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

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

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

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

4 結(jié)束語

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