基于移動(dòng)匯聚節(jié)點(diǎn)和分簇的改進(jìn)節(jié)能路由算法

劉天琪　張寧博　姬聰敏　上官國(guó)慶

【摘要】為了緩解“能量空洞”現(xiàn)象，本文提出了一種基于移動(dòng)匯聚節(jié)點(diǎn)的節(jié)能路由算法，在現(xiàn)有節(jié)能路由算法的基礎(chǔ)上對(duì)匯聚節(jié)點(diǎn)的運(yùn)動(dòng)軌跡和簇頭與匯聚節(jié)點(diǎn)的連接方式進(jìn)行改進(jìn)，增加了網(wǎng)絡(luò)的覆蓋率。為了平衡無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)能量，本文令剩余能量最大的節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)。根據(jù)節(jié)點(diǎn)間距離的不同，本文分情況討論了節(jié)點(diǎn)的能量消耗，最終使用弗洛伊德算法得到了耗能最小的簇頭與匯聚節(jié)點(diǎn)的路由。從仿真實(shí)驗(yàn)可以看出，本算法能夠有效地延長(zhǎng)網(wǎng)絡(luò)周期，減緩死亡節(jié)點(diǎn)的出現(xiàn)。

【關(guān)鍵詞】移動(dòng)匯聚節(jié)點(diǎn);無線傳感網(wǎng)

物聯(lián)網(wǎng)技術(shù)在近幾年已經(jīng)成為信息技術(shù)的重要組成部分，而無線傳感網(wǎng)（簡(jiǎn)稱WSN）則是物聯(lián)網(wǎng)技術(shù)中的核心部分，因此對(duì)于無線傳感網(wǎng)絡(luò)中的路由協(xié)議和路由算法的研究也成為了熱門問題。

無線傳感網(wǎng)由許多個(gè)傳感器節(jié)點(diǎn)組成，可以根據(jù)不同的要求監(jiān)測(cè)不同的數(shù)據(jù)，例如溫度、濕度等，傳感器可以將這些數(shù)據(jù)發(fā)送給網(wǎng)絡(luò)內(nèi)的匯聚節(jié)點(diǎn)，再由匯聚節(jié)點(diǎn)轉(zhuǎn)發(fā)給用戶或其他設(shè)備。傳統(tǒng)路由協(xié)議的無線傳感網(wǎng)中，匯聚節(jié)點(diǎn)是固定的，如圖1中的紅色點(diǎn)所示，藍(lán)色的點(diǎn)表示網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)，黑色的點(diǎn)表示普通節(jié)點(diǎn)。其中簇頭節(jié)點(diǎn)不僅要接收來自普通節(jié)點(diǎn)的信息，還要將信息轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)，能量消耗過快，從而大大降低了這些節(jié)點(diǎn)的生命周期，這些節(jié)點(diǎn)被稱為熱節(jié)點(diǎn)，這種現(xiàn)象被稱為“能量空洞”，有礙于無線傳感網(wǎng)的正常工作。

為了緩解上述“能量空洞”現(xiàn)象，本文提出了一種基于移動(dòng)匯聚節(jié)點(diǎn)的策略，避免長(zhǎng)距離通信消耗大量能量，同時(shí)增大了網(wǎng)絡(luò)的覆蓋率。

1. 算法概述

本文規(guī)定移動(dòng)匯聚節(jié)點(diǎn)的運(yùn)動(dòng)軌跡是既定的，可以根據(jù)網(wǎng)絡(luò)部署的時(shí)間推算匯聚節(jié)點(diǎn)的位置。根據(jù)網(wǎng)絡(luò)部署環(huán)境的需求，本文人為地將網(wǎng)絡(luò)劃分為N個(gè)相等的部分，一個(gè)部分為一個(gè)簇，每個(gè)簇內(nèi)只有一個(gè)簇頭節(jié)點(diǎn)。在選取簇頭時(shí)，為了保持網(wǎng)絡(luò)的能量均衡，每輪都只選擇剩余能量最高的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)。同時(shí)為了擴(kuò)大信息接收的范圍，本文令匯聚節(jié)點(diǎn)以圓形軌跡在網(wǎng)絡(luò)內(nèi)運(yùn)動(dòng)，且軌跡半徑為網(wǎng)絡(luò)半徑的一半。

成簇以后，每個(gè)簇的簇頭要與匯聚節(jié)點(diǎn)進(jìn)行通信，此時(shí)會(huì)出現(xiàn)與匯聚節(jié)點(diǎn)較遠(yuǎn)的簇頭節(jié)點(diǎn)，為減少能量消耗，本文首先選擇與匯聚節(jié)點(diǎn)較近的簇頭節(jié)點(diǎn)作為鏈頭，其他簇頭節(jié)點(diǎn)通過弗洛伊德算法計(jì)算到鏈頭耗能最小的路由，最終通過鏈頭與匯聚節(jié)點(diǎn)相連。

2. 算法模型

2.1 網(wǎng)絡(luò)模型

本文規(guī)定無線傳感網(wǎng)絡(luò)為圓形，該圓形區(qū)域的半徑為R，內(nèi)含n個(gè)傳感器節(jié)點(diǎn)，這些傳感器節(jié)點(diǎn)都完全相同且不能移動(dòng)。匯聚節(jié)點(diǎn)的運(yùn)動(dòng)軌跡為與該網(wǎng)絡(luò)同圓心的圓形，且軌跡半徑r為該網(wǎng)絡(luò)半徑的一半，即：

匯聚節(jié)點(diǎn)的初始位置為軌跡上的隨機(jī)位置。

2.2 移動(dòng)匯聚節(jié)點(diǎn)

無線傳感網(wǎng)的圓形邊緣記為O，移動(dòng)匯聚節(jié)點(diǎn)的移動(dòng)軌跡記為o，匯聚節(jié)點(diǎn)的移動(dòng)速度，即線速度記為v，規(guī)定其在該網(wǎng)絡(luò)中按逆時(shí)針移動(dòng)。當(dāng)匯聚節(jié)點(diǎn)經(jīng)過ΔT的時(shí)間間隔后，根據(jù)線速度公式和圓的特性，有：

其中表示時(shí)間內(nèi)匯聚節(jié)點(diǎn)移動(dòng)的弧形長(zhǎng)度，表示時(shí)間內(nèi)匯聚節(jié)點(diǎn)在O上變化的角度。

2.3 分簇和簇頭的選取

本文將整個(gè)網(wǎng)絡(luò)均分為N個(gè)等面積的扇形，每個(gè)扇形中的傳感器節(jié)點(diǎn)構(gòu)成一個(gè)簇，因此在網(wǎng)絡(luò)中共有N個(gè)簇，一個(gè)簇有一個(gè)簇頭節(jié)點(diǎn)。本文假設(shè)N=6，（如圖2）則有：

如圖2所示，藍(lán)色直線分出的6個(gè)相等扇形區(qū)域就是6個(gè)簇，按逆時(shí)針進(jìn)行標(biāo)號(hào)，每個(gè)簇都有一個(gè)簇頭節(jié)點(diǎn)，簇內(nèi)的普通節(jié)點(diǎn)會(huì)把數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)。在選簇頭時(shí)，本文首先隨機(jī)選擇每個(gè)簇的簇頭作為候選簇頭節(jié)點(diǎn)nh，根據(jù)剩余能量的大小令其他節(jié)點(diǎn)與該節(jié)點(diǎn)進(jìn)行簇頭節(jié)點(diǎn)的競(jìng)爭(zhēng)，如果在同一個(gè)簇內(nèi)，節(jié)點(diǎn)ni比nh的剩余能量大，則ni節(jié)點(diǎn)成為新的候選簇頭，經(jīng)過一輪比較，最后本簇內(nèi)剩余能量最高的節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)ni。在圖2中，有粉色圈的節(jié)點(diǎn)就是簇頭節(jié)點(diǎn)。

2.4 能量消耗

簇內(nèi)節(jié)點(diǎn)與簇頭節(jié)點(diǎn)的通信需要消耗能量，本文只考慮傳輸數(shù)據(jù)所消耗的能量。傳輸數(shù)據(jù)所消耗的能量與距離有很大的關(guān)系，若（xi，yi）是傳感器節(jié)點(diǎn)ni的坐標(biāo)，（xi，yj）是傳感器節(jié)點(diǎn)nj的坐標(biāo)，則這兩個(gè)節(jié)點(diǎn)之間的距離公式為：

傳輸數(shù)據(jù)分為兩種情況，分別是普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)直接通信，普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)間接通信。

（1）普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)直接通信

首先計(jì)算普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)的距離D（ni，nl），將其與距離閾值do進(jìn)行比較，若D（ni，nl）小于距離閾值do，則采用自由空間模型，反之則采用雙徑傳播模型計(jì)算能量的消耗。因此普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)直接通信時(shí)的能量消耗公式為：

其中Ele表示射頻能耗系數(shù)，Data表示發(fā)送和接受的數(shù)據(jù)長(zhǎng)度，表示自由空間模型的功率放大電路能耗系數(shù)，表示雙徑傳播模型的功率放大電路能耗系數(shù)。

（2）普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)間接通信

當(dāng)某些普通節(jié)點(diǎn)與簇頭節(jié)點(diǎn)距離較遠(yuǎn)時(shí)，可以采用令其與其他普通節(jié)點(diǎn)通信的方式來間接傳輸數(shù)據(jù)。普通節(jié)點(diǎn)ni選擇其他節(jié)點(diǎn)nj，ni先將數(shù)據(jù)發(fā)送給nj，再由nj將數(shù)據(jù)轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)nl，此時(shí)的能量消耗分為三部分，ni發(fā)送數(shù)據(jù)給nj，nj發(fā)送數(shù)據(jù)給nl，nj接收數(shù)據(jù)。發(fā)送數(shù)據(jù)的能量消耗公式如公式（4）所示，接收數(shù)據(jù)的能量消耗公式為：

最后，經(jīng)過多輪數(shù)據(jù)傳輸，若有節(jié)點(diǎn)能量消耗為0，則認(rèn)為該節(jié)點(diǎn)死亡，不參與后面的通信過程。

2.5 連接簇頭

匯聚節(jié)點(diǎn)是移動(dòng)的，因此不可避免地會(huì)出現(xiàn)與匯聚節(jié)點(diǎn)較遠(yuǎn)的簇頭節(jié)點(diǎn)，若令所有簇頭與匯聚節(jié)點(diǎn)直接通信，則會(huì)導(dǎo)致簇頭節(jié)點(diǎn)死亡過快，出現(xiàn)“能量空洞”。對(duì)于長(zhǎng)距離通信的現(xiàn)象，可以令所有簇頭都與和匯聚節(jié)點(diǎn)最近的簇頭通信，使用弗洛伊德算法選擇能耗最小的路由，再由這個(gè)最近的簇頭節(jié)點(diǎn)傳輸數(shù)據(jù)給匯聚節(jié)點(diǎn)，這個(gè)距匯聚節(jié)點(diǎn)最近的簇頭節(jié)點(diǎn)稱為鏈頭節(jié)點(diǎn)。簇頭連接的具體步驟如下：

（1）計(jì)算每個(gè)簇頭與匯聚節(jié)點(diǎn)的距離，選出與匯聚節(jié)點(diǎn)距離最近的鏈頭節(jié)點(diǎn);

（2）計(jì)算簇頭節(jié)點(diǎn)傳輸數(shù)據(jù)的耗能情況;

（3）使用弗洛伊德算法，得到耗能量最小的每個(gè)其他簇頭與的路由，并記錄路由的路徑;

（4）更新簇頭節(jié)點(diǎn)的剩余能量;

（5）連接簇頭和鏈頭節(jié)點(diǎn)，最后連接匯聚節(jié)點(diǎn)與鏈頭節(jié)點(diǎn)，至此完成所有通信網(wǎng)絡(luò)的部署。

3. 仿真實(shí)驗(yàn)

本文使用MATLAB對(duì)上述算法進(jìn)行仿真實(shí)驗(yàn)，假設(shè)該網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)數(shù)n=100，區(qū)域半徑r=50，匯聚節(jié)點(diǎn)的軌跡半徑r=25，傳輸?shù)臄?shù)據(jù)大小為5bit。

圖3是運(yùn)行結(jié)果中的其中一張圖，粉色圈表示簇頭節(jié)點(diǎn)，藍(lán)色圈表示該節(jié)點(diǎn)已經(jīng)死亡，紅色五角星表示鏈頭節(jié)點(diǎn)，紅色實(shí)心點(diǎn)表示匯聚節(jié)點(diǎn)的初始位置，黃色圈表示匯聚節(jié)點(diǎn)現(xiàn)在的位置。

由于設(shè)備的運(yùn)行速度有限，本文將每輪傳輸數(shù)據(jù)的時(shí)間間隔ΔT增大，節(jié)點(diǎn)的初始能量減小以減少傳輸數(shù)據(jù)的輪數(shù)。在相同的環(huán)境下，通過多次運(yùn)行，本文比較了本算法和傳統(tǒng)LEACH算法出現(xiàn)死亡節(jié)點(diǎn)的平均輪次，在大約50輪的時(shí)候LEACH算法出現(xiàn)了死亡節(jié)點(diǎn)，而本算法在75輪才出現(xiàn)死亡節(jié)點(diǎn)，由此可以證明本算法能夠較好地延長(zhǎng)網(wǎng)絡(luò)生命周期。

參考文獻(xiàn)：

[1]吳瑞睿，劉潔琳.無線傳感器網(wǎng)絡(luò)綜述[J].科技創(chuàng)新與應(yīng)用，2018，000（014）：65-66.

[2]王施雨，劉唐.基于數(shù)據(jù)引流的無線傳感器網(wǎng)絡(luò)能量空洞避免研究[J].四川師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2019，42（01）：138-146.