張慧娟

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

0 引言

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

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

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

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

圖1 基于簇的網(wǎng)絡拓撲結構

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

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

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

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

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

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

1.1 能量消耗模型

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

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

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

1.2 相關概念

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

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

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

2 CRBD 路由

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

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

2.2 初始的簇頭數(shù)

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

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

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

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

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

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

2.6 構建最短路徑示例

圖2 構建最短路徑的多跳路由示例

表1 最短路徑的迭代過程

3 性能仿真

3.1 仿真參數(shù)

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

表2 仿真參數(shù)

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

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

接下來，數(shù)據(jù)包傳遞率、能量消耗和網(wǎng)絡壽命以及數(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ù)包傳遞率隨運行輪的增加而下降速度更快，其中CADC 算法的下降速度最快。原因在于：CADC路由旨在通過控制擁塞，提高數(shù)據(jù)傳輸率。因此，在前60 輪內(nèi)，CADC 路由的數(shù)據(jù)包傳遞率優(yōu)于EIFC路由，但是隨著輪數(shù)的增加，其數(shù)據(jù)包傳遞率迅速下降。這主要是因為：CADC 路由并沒有考慮到節(jié)點能耗問題，當運行至一定輪數(shù)，網(wǎng)絡內(nèi)部分節(jié)點的能耗可能消耗殆盡，無法轉發(fā)數(shù)據(jù)包，導致數(shù)據(jù)包傳遞率快速下降。

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

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

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

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

3.4 網(wǎng)絡壽命

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

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

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

圖6 網(wǎng)絡壽命

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

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

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

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

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

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

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

4 結論

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