無線傳感網(wǎng)絡(luò)中基于Dijkstra 算法的分簇路由

張慧娟

（駐馬店職業(yè)技術(shù)學(xué)院信息工程系，河南 駐馬店 463000）

0 引言

無線傳感網(wǎng)絡(luò)（wireless sensor networks，WSNs）是由大量傳感節(jié)點(diǎn)以自組織方式分布，且節(jié)點(diǎn)間能相互通信的無線網(wǎng)絡(luò)。目前，WSNs 已在多個領(lǐng)域內(nèi)廣泛使用，如健康醫(yī)療，野外環(huán)境監(jiān)測。傳感節(jié)點(diǎn)通過連續(xù)地監(jiān)測環(huán)境，并感測環(huán)境數(shù)據(jù)，再將數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)，進(jìn)而實(shí)現(xiàn)對環(huán)境的監(jiān)測。

節(jié)點(diǎn)的通信帶寬有限，若信宿在節(jié)點(diǎn)通信范圍內(nèi)，節(jié)點(diǎn)就直接將數(shù)據(jù)傳輸至匯聚節(jié)點(diǎn)，否則節(jié)點(diǎn)只能以多跳方式向匯聚節(jié)點(diǎn)傳輸數(shù)據(jù)。在部分應(yīng)用中，如目標(biāo)跟蹤，戰(zhàn)場偵察，WSNs 將產(chǎn)生了大量的數(shù)據(jù)，這增加了網(wǎng)絡(luò)流量。

由于節(jié)點(diǎn)能耗是WSNs 的有限資源，基于WSNs 的網(wǎng)絡(luò)應(yīng)用必須關(guān)注節(jié)點(diǎn)能耗問題。節(jié)點(diǎn)的能量有限，即便節(jié)點(diǎn)能量消耗完畢，也不便于補(bǔ)給能量。因此，必須通過算法或者策略緩解節(jié)點(diǎn)能耗速度，延長節(jié)點(diǎn)的工作時間。

簇結(jié)構(gòu)是降低節(jié)點(diǎn)能耗，提高數(shù)據(jù)傳輸效率的有效策略。在簇結(jié)構(gòu)中，將WSNs 內(nèi)節(jié)點(diǎn)劃分多個簇，每個簇由一個簇頭（cluster head，CH）和多個簇成員構(gòu)成。CH 負(fù)責(zé)收集、融合本簇內(nèi)的簇成員數(shù)據(jù)，再傳輸至匯聚節(jié)點(diǎn)，圖1 給出典型的基于簇的WSNs 拓?fù)浣Y(jié)構(gòu)。

圖1 基于簇的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

然而，由于CHs 承擔(dān)了更多數(shù)據(jù)收集和轉(zhuǎn)發(fā)的任務(wù)，它們能耗速度高于簇成員節(jié)點(diǎn)的能耗速度。并且，各個CH 間的能耗速度可能也不盡相同。因此，如何選擇最優(yōu)的簇頭數(shù)，并且平衡CHs 間的能耗是構(gòu)建簇算法必須考慮的問題。

文獻(xiàn)［6］討論了基于能量消耗的簇頭選擇問題，并提出間歇性簇頭選擇策略。文獻(xiàn)［7］提出基于雞群優(yōu)化算法的簇頭選舉策略，利用雞群優(yōu)化算法產(chǎn)生簇頭，穩(wěn)定簇結(jié)構(gòu)，進(jìn)而減少網(wǎng)絡(luò)能耗。

盡管分簇路由能夠減少網(wǎng)絡(luò)能耗，并且研究人員也提出不同的分簇路由策略，但是這些策略并沒有考慮節(jié)點(diǎn)的擁塞情況。實(shí)質(zhì)上，若節(jié)點(diǎn)擁塞，會導(dǎo)致節(jié)點(diǎn)無法按時傳輸數(shù)據(jù)包，增加數(shù)據(jù)包傳輸時延，并且也增加了節(jié)點(diǎn)能耗。

為此，基于Dijkstra 算法的分簇路由（clustering routing-based dijkstra，CRBD）。CRBD 路由依據(jù)節(jié)點(diǎn)的剩余能量以及離匯聚節(jié)點(diǎn)的距離信息，產(chǎn)生簇頭，并且避免擁塞節(jié)點(diǎn)擔(dān)任簇頭。再利用貪婪啟發(fā)式算法構(gòu)建簇。為了縮短簇間的數(shù)據(jù)傳輸路徑，采用Dijkstra 算法構(gòu)建簇間最短路徑，優(yōu)化傳輸路徑，減少簇頭的能量消耗。仿真結(jié)果表明，CRBD 路由降低節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)壽命。

1 系統(tǒng)模型及相關(guān)概念

式中，表示節(jié)點(diǎn)的通信半徑。

1.1 能量消耗模型

節(jié)點(diǎn)s接收比特數(shù)據(jù)所消耗的能量：

式中，α表示接收單比特數(shù)據(jù)所消耗的能量。

節(jié)點(diǎn)s在傳輸數(shù)據(jù)和接收數(shù)據(jù)兩個階段共消耗的能量E：

1.2 相關(guān)概念

數(shù)據(jù)包傳遞率（packet delivery rate，PDR）等于匯聚節(jié)點(diǎn)所接收的數(shù)據(jù)包數(shù)與所有節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)包數(shù)之比，如式（7）所示：

式中，N表示匯聚節(jié)點(diǎn)所接收的數(shù)據(jù)包數(shù)，N表示所有節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)包數(shù)，其定義如式（8）所示：

將時間內(nèi)信宿所接收的數(shù)據(jù)包數(shù)定義為網(wǎng)絡(luò)吞吐量：

2 CRBD 路由

CRBD 路由主要由擁塞節(jié)點(diǎn)的識別、最初CHs數(shù)、產(chǎn)生最優(yōu)CHs、簇形成和數(shù)據(jù)傳輸4 個階段構(gòu)成。

2.1 擁塞節(jié)點(diǎn)的識別

2.2 初始的簇頭數(shù)

式中，表示節(jié)點(diǎn)通信半徑。

2.3 產(chǎn)生最優(yōu)簇頭

為了避免擁塞節(jié)點(diǎn)擔(dān)任簇頭，CRBD 路由禁止擁塞節(jié)點(diǎn)擔(dān)任簇頭。即擁塞節(jié)點(diǎn)不參與簇頭競爭。

2.4 基于貪婪啟發(fā)式算法的簇形成

節(jié)點(diǎn)s依據(jù)式（16）計(jì)算與個簇頭間的權(quán)重值，再從中選擇具有最大權(quán)重的簇頭作為自己的簇頭，并向發(fā)送加入消息Join_CH。

2.5 最短路徑的簇頭間多跳路由

2.6 構(gòu)建最短路徑示例

圖2 構(gòu)建最短路徑的多跳路由示例

表1 最短路徑的迭代過程

3 性能仿真

3.1 仿真參數(shù)

利用MATLAB 軟件建立仿真平臺，分析CRBD路由的性能。在100×100方形區(qū)域內(nèi)隨機(jī)部署100～200 個節(jié)點(diǎn)。匯聚節(jié)點(diǎn)位于區(qū)域中心。圖3 顯示了在100×100方形區(qū)域內(nèi)隨機(jī)部署100 個節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，其中，紅色的空心圓表示匯聚節(jié)點(diǎn)，黑色實(shí)心點(diǎn)表示傳感節(jié)點(diǎn)。具體的仿真參數(shù)如下頁表2 所示。

表2 仿真參數(shù)

圖3 100 個節(jié)點(diǎn)100×100 m2 在區(qū)域內(nèi)的分布

為了更好地分析CRBD 路由性能，選擇文獻(xiàn)［13］提出的基于改進(jìn)螢火蟲聚類的能效路由（energy efficient routing based on improved firefly clustering，EIFC）和文獻(xiàn)［14］提出擁塞感知的數(shù)據(jù)收集（congestion-aware data collection，CADC）路由。EIFC 路由利用改進(jìn)螢火蟲聚類算法分簇，使簇頭分布更均勻，但是EIFC 路由并沒有優(yōu)化數(shù)據(jù)傳輸路徑。CADC 路由旨在提高數(shù)據(jù)收集效率，其利用kmeans 聚類優(yōu)化數(shù)據(jù)傳輸率，控制擁塞。

接下來，數(shù)據(jù)包傳遞率、能量消耗和網(wǎng)絡(luò)壽命以及數(shù)據(jù)包傳輸時延4 個方面分析CRBD 路由、EIFC 路由和CADC 路由的性能。

3.2 數(shù)據(jù)包傳遞率

首先分析CRBD 路由，EIFC 路由和CADC 路由的數(shù)據(jù)包傳遞率性能，如圖4 所示。

圖4 數(shù)據(jù)包傳遞率

從圖4 可知，相比于CADC 路由和EIFC 路由，CRBD 路由的數(shù)據(jù)包傳遞率具有明顯的優(yōu)勢。在100 輪（=100）內(nèi)，CRBD 路由的數(shù)據(jù)包傳遞率均保持在85%以上。相比之下，CADC 路由和EIFC 路由的數(shù)據(jù)包傳遞率隨運(yùn)行輪的增加而下降速度更快，其中CADC 算法的下降速度最快。原因在于：CADC路由旨在通過控制擁塞，提高數(shù)據(jù)傳輸率。因此，在前60 輪內(nèi)，CADC 路由的數(shù)據(jù)包傳遞率優(yōu)于EIFC路由，但是隨著輪數(shù)的增加，其數(shù)據(jù)包傳遞率迅速下降。這主要是因?yàn)椋篊ADC 路由并沒有考慮到節(jié)點(diǎn)能耗問題，當(dāng)運(yùn)行至一定輪數(shù)，網(wǎng)絡(luò)內(nèi)部分節(jié)點(diǎn)的能耗可能消耗殆盡，無法轉(zhuǎn)發(fā)數(shù)據(jù)包，導(dǎo)致數(shù)據(jù)包傳遞率快速下降。

與CADC 路由相比，CRBD 路由和EIFC 路由的數(shù)據(jù)包傳遞率下降速度較緩慢。這歸功于：它們優(yōu)化了簇頭的選擇，緩解了節(jié)點(diǎn)的能耗速度。

3.3 節(jié)點(diǎn)的平均能耗率

下頁圖5 給出CRBD 路由，EIFC 路由和CADC路由的平均能耗性能。從圖可知，相比于CADC 路由，CRBD 路由的平均能耗最低，并且隨運(yùn)行輪的增加，能耗增加速度也較緩慢。但是，在前40 輪階段，CRBD 路由的平均能耗略高于EIFC 路由。這主要是因?yàn)椋篊RBD 路由中節(jié)點(diǎn)需要執(zhí)行基于貪婪啟發(fā)式算法，增加了節(jié)點(diǎn)能耗。但是隨著輪數(shù)的增加，CRBD 路由在降低能耗方面的優(yōu)勢突顯出來。

圖5 節(jié)點(diǎn)的平均能耗

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

網(wǎng)絡(luò)壽命是衡量WSNs 性能的重要指標(biāo)。引用式（20）計(jì)算網(wǎng)絡(luò)壽命（Network Lifetime，NL）。

式中，表示節(jié)點(diǎn)的初始能量。從式（20）可知，等于節(jié)點(diǎn)的初始能量與網(wǎng)絡(luò)內(nèi)能耗最多節(jié)點(diǎn)所消耗的能量的比值。

在100×100區(qū)域部署100～200 個節(jié)點(diǎn)。在每個拓?fù)洵h(huán)境下，運(yùn)行100 輪，再利用式（20）計(jì)算網(wǎng)絡(luò)壽命。圖6 給出CRBD 路由，EIFC 路由和CADC算法的情況。

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

從圖6 可知，CRBD 路由的網(wǎng)絡(luò)壽命性能優(yōu)于EIFC 路由和CADC 路由。這符合預(yù)期，也與圖5 的數(shù)據(jù)相符合。此外，節(jié)點(diǎn)數(shù)的增加，使網(wǎng)絡(luò)壽命呈下降趨勢。原因在于：節(jié)點(diǎn)數(shù)越多，算法的復(fù)雜度越高，加大了節(jié)點(diǎn)運(yùn)行開銷。但是從圖6 可知，網(wǎng)絡(luò)壽命隨節(jié)點(diǎn)數(shù)增加而下降的速度較緩慢。

3.5 數(shù)據(jù)包傳輸時延

最后，分析數(shù)據(jù)包的傳輸時延，其反映了將一個數(shù)據(jù)包從節(jié)點(diǎn)傳輸至匯聚節(jié)點(diǎn)所需的平均時間。在100×100區(qū)域部署100～200 個節(jié)點(diǎn)。在每個拓?fù)洵h(huán)境下，運(yùn)行100 輪。依據(jù)式（11）計(jì)算一個數(shù)據(jù)包的平均傳輸時延。

圖7 給出CRBD 路由，EIFC 路由和CADC 路由的平均傳輸時延隨節(jié)點(diǎn)數(shù)的變化情況。從圖可知，節(jié)點(diǎn)數(shù)的增加提升了平均傳輸時延。這主要原因在于：節(jié)點(diǎn)數(shù)越多，產(chǎn)生的數(shù)據(jù)包數(shù)越多，隊(duì)列時延隨之增加。

圖7 數(shù)據(jù)包的平均傳輸時延

此外，從圖6 可知，節(jié)點(diǎn)數(shù)的增加，加大了節(jié)點(diǎn)的能耗，提升了節(jié)點(diǎn)能量消耗速度。而能耗速度的加大，可能導(dǎo)致部分節(jié)點(diǎn)的剩余能量過低，無法轉(zhuǎn)發(fā)數(shù)據(jù)或者傳輸數(shù)據(jù)，最終，降低了數(shù)據(jù)包傳輸成功率，需要多次重傳，甚至傳輸失敗。這就增加了數(shù)據(jù)包的傳輸時延。

相比于EIFC和CADC 路由，CRBD 路由的平均傳輸時延性能存在優(yōu)勢。這歸功于：1）CRBD 路由引用了擁塞控制機(jī)制，避免了擁塞節(jié)點(diǎn)擔(dān)任簇頭，降低了隊(duì)列時延；2）CRBD 路由引用了Dijkstra 算法構(gòu)建最短簇間路徑，縮短了數(shù)據(jù)傳輸路徑。

4 結(jié)論

為了緩解節(jié)點(diǎn)的能耗，本文提出Dijkstra 算法的分簇路由CRBD。CRBD 路由從優(yōu)化簇和構(gòu)建簇間多路由兩個階段減少節(jié)點(diǎn)能耗。利用節(jié)點(diǎn)的剩余能量以及離匯聚節(jié)點(diǎn)間距離信息計(jì)算節(jié)點(diǎn)權(quán)重，再依據(jù)權(quán)重，擇優(yōu)部分節(jié)點(diǎn)作為簇頭。并利用貪婪啟發(fā)式算法，構(gòu)建簇，優(yōu)化簇內(nèi)數(shù)據(jù)傳輸路徑。同時，利用Dijkstra 算法構(gòu)建簇間路徑，減少簇頭的能量消耗。仿真結(jié)果表明，提出的CRBD 路由減少了節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)壽命，并提升了數(shù)據(jù)包傳遞率。