劉玉紅，陳滿銀，李翠然

(蘭州交通大學 電子與信息工程學院，蘭州 730070)

無線傳感器網絡(wireless sensor networks，WSN)由數百甚至數千個傳感器節點組成，收集監測數據供終端用戶分析，被廣泛應用于醫療保健、智能家居、農業工程和目標跟蹤等各個領域[1-4].WSN有很多優勢，包括自配置、組網靈活、經濟有效、體積小等，而由于傳感器節點的能量由電池供應，電池的能量是有限的，并且傳感器網絡經常部署在條件惡劣和無人堅守的環境，如救災行動、礦產開采[5-6]，存在節點能量一旦耗盡便很難及時補充或更換的問題；因此延長網絡壽命，提高能量利用率，實現高效能網絡是WSN研究的主要目標之一.分層路由算法是解決這一問題的重要方法，它在網絡中首先選舉出若干個簇頭，傳感器節點根據簇頭選擇加入簇，然后將收集到的數據發送到簇頭節點，簇頭再將數據進行融合后轉發到基站(base station,BS)，通過優化網絡通信量達到節省網絡能耗的目的[7].由于分層路由算法的實際應用效果優于平面路由算法，所以分層路由算法已經成為WSN節能路由算法研究的熱點之一[8].

文獻[9]提出了最具經典意義的LEACH算法，該算法提出了“輪循環”的思想，每輪根據閾值和賦給各節點的隨機值來確定簇頭，將網絡能耗分攤到各個節點上，但因為在選擇簇頭時，沒有考慮簇頭的剩余能量和位置，導致能量較低的節點擔任簇頭而過早死亡以及分簇不均帶來的簇頭負載不均衡等問題.文獻[10]在K-means算法的基礎上，提出了EECPK-means算法，根據與基站之間的距離確定初始簇頭，迭代計算得到最終簇頭，在一定程度上使簇頭的分布更加均勻；但存在節點連續多次充當簇頭而過早死亡的問題.文獻[11]提出了一種基于能量質心的路由算法，在選舉簇頭時，根據節點的剩余能量與位置信息計算出能量質心，將距離能量質心最近的節點作為簇頭，減小網絡的能量消耗；但存在簇頭負載不平衡而影響網絡壽命的問題.

本文在對上述文獻進行分析研究后，提出一種基于均勻分區的無線傳感器網絡節能路由算法，首先通過改進的多叉樹遍歷算法選擇隨機且分布均勻的初始簇頭，避免出現節點連續多次被選為簇頭的問題；其次，節點根據自身與初始簇頭之間的距離以及成員節點的數量來加入分區，均衡各分區內節點的個數，進而均衡各簇頭的負載；接下來，再在各分區內優先選擇剩余能量較多以及與其他節點之間的距離和最小的節點擔任簇頭，有效地減小網絡能耗；最后進行數據收集和上傳，其中，距離BS較遠的簇頭采用多跳通信的方式將數據轉發到BS.

1 WSN能耗模型及參數設置

1.1 無線通信能耗模型

因為節點的能量消耗主要集中在數據的接收和發送上[12]，所以本文對節點的能耗分析主要考慮節點的無線通信能耗.節點發送l/bit數據到與其距離為d/m的節點，其消耗的能量ETX(l,d)為：

(1)

其中：Eelec是發送和接收數據時電路消耗的能量;εfs與εmp分別表示自由空間和多徑衰落模型下的放大器系數;距離閾值[13]Dthreshold為

(2)

節點接收l/bit數據所消耗的能量ERX(l)為

ERX(l)=lEelec.

(3)

節點對m個數據包進行數據融合所消耗的能量Efuse為

Efuse(m)=m×lEDA,

(4)

其中，EDA是融合單位比特數據所消耗的能量.

1.2 仿真場景參數設置

本文在進行能耗分析和仿真實驗過程中，仿真場景參數設置見表1.

表1 仿真場景參數設置

2 WSN能耗分析

2.1 簇頭節點能耗分析

在無線傳感器網絡分層路由算法中，簇頭節點主要負責接收該簇成員節點收集到的傳感數據，并將融合后的數據轉發到基站.所以，簇頭節點的能耗主要包括接收數據的能耗、融合數據的能耗和向下一簇頭發送數據的能耗.根據公式(1)、(3)、(4)，如果簇內成員節點的個數為n，簇頭的發送距離為d，則該簇頭節點在一輪中消耗的能量[14]ECH(n,d)為

ECH(n,d)=ETX+ERX+Efuse=(n+1)×lEelec+nlEDA+lεfsd2.

(5)

由式(5)可以得到，簇頭能耗與簇內節點的數量n和簇頭的發送距離d的關系分別為：

(6)

其中：1≤n≤100；0≤d≤Dthreshold.則ECH(n)和ECH(d)的取值范圍分別為：

(7)

由式(7)可知，簇內節點的數量對簇頭能耗的影響要遠大于發送距離對其的影響.所以均衡簇內節點的數量對均衡簇頭的能量消耗起著主導性的作用.

2.2 簇頭位置對網絡能耗的影響分析

假設一個簇中10個節點隨機分布在10 m×10 m的監測區域內，如圖1所示，計算這10個節點分別充當簇頭時，簇頭節點與其他節點之間的距離之和與網絡能耗，如圖2所示.

圖1 節點分布位置圖

圖2 簇頭位置和網絡能耗關系對比圖

從圖2中可以看出，網絡能耗與距離和(簇頭節點與其他簇內節點之間的距離之和)成正比關系.其中，節點10與其他節點之間的距離和最小，當簇頭位置在節點10上時，網絡能耗也是最小的.所以，在簇頭選舉時，選擇距離和越小的節點作為簇頭越能降低網絡的能耗.

3 基于均勻分區的WSN路由算法

3.1 均勻分區

根據2.1節中關于簇頭節點能耗的分析可知，簇內節點的數量是影響簇頭能耗的主要因素.由此，本文提出均勻分區的方法，通過均衡各分區內節點的數量，同時在各分區中選取能使網絡能耗最小的節點充當簇頭，從而均衡簇頭負載能耗，有效減小網絡能耗.

3.1.1 最優簇頭數的確定

根據監測區域的大小和節點的數量計算出所需的簇頭數，設有N個節點隨機分布在M×N的區域中，得到最優簇頭數[15]kopt為

(8)

其中，dtoBS是節點到基站之間的平均距離.

3.1.2 初始簇頭的選擇

假設在M×M的監測區域中，隨機分布N個節點，需要從其中隨機選取kopt個節點作為簇頭，要求這kopt個節點兩兩之間距離大于間隔值Dmin.

本文采用改進的多叉樹遍歷算法來求解初始簇頭的位置，該算法的具體求解思路是：先隨機選擇一個根節點，根據節點間的距離信息，將與該節點(父節點)距離大于約束距離Dmin的節點均設為該節點的子節點；再根據同樣的距離約束條件，設定每個子節點(此時為父節點)的下一級子節點；以此類推，完成節點多叉樹的構建，如圖3(a)所示.接下來，要找到一條滿足所有子節點與父節點的距離大于Dmin約束條件且層數為kopt的路徑，判斷該條路徑中kopt個節點是否滿足兩兩之間距離均大于Dmin的總條件，若滿足，則記錄節點信息，停止循環；否則，選擇下一條路徑并判斷其中的節點是否滿足以上條件.

如圖3(b)所示，先隨機選出一個節點a1，根據子節點與父節點之間的距離大于Dmin的約束條件，找到第一條路徑a1→a2→a4，其中a1和a2、a2和a4滿足距離大于Dmin的約束條件.下一步判斷a1、a2、a4這三個節點是否滿足兩兩之間距離均大于Dmin的總條件.從圖3(a)中可看出，與a1節點距離大于間隔值Dmin的節點有a2、a3、a5，其中沒有a4，所以，節點a1與a4之間的距離不符合條件.檢查下一條路徑a1→a2→a5，其中a1和a2、a2和a5滿足距離大于Dmin的約束條件，同時a5又是a1節點的子節點，所以a1和a5之間的距離也符合距離大于Dmin的約束條件.所以，節點a1、a2與a5之間符合兩兩之間距離大于Dmin的約束條件，選為初始簇頭，示于圖3(b)中的陰影節點，記錄節點信息，并停止循環.可見，改進后的多叉樹遍歷算法在被選取節點的隨機性前提下，可以使選出的節點分布更加均勻.

圖3 多叉樹示例圖

根據以上多叉樹遍歷算法求解初始簇頭的位置.其中，根據監測區域的面積以及最優簇頭數計算出的間隔值Dmin為

(9)

3.1.3 節點選擇分區

計算節點與各初始簇頭之間的距離權值，節點根據最小的距離權值選擇加入的分區.本文定義的距離權值函數W(nodei,aj)為：

(10)

其中：dis(nodei,aj)是節點nodei與初始簇頭之間的距離；ni是初始簇頭aj所在區域當前擁有的節點個數；uj為該分區節點數量的上限，如式(11)所示.

(11)

其中，Nalive是當前輪網絡中存活節點的個數.

由式(10)和式(11)可知，當各區域節點個數未達到上限值時，節點根據距離最近原則加入分區；當該區域節點個數達到上限值時，則不再接收新的節點加入,這樣就可以有效地控制各區域節點的數量.

3.2 簇頭競選

根據均勻分區可得到kopt個節點數量均勻的區域，在每個區域中選擇一個能耗權值最小的節點充當簇頭節點.由2.2節知，簇頭節點與其成員節點之間的距離和越小，網絡的能量消耗就越小，同時考慮到簇頭節點的剩余能量，可得到競選簇頭時節點的能耗權值WCH(nodei)為

(12)

3.3 節點通信

在WSN分層路由算法中，節點通信可分為簇內通信和簇間通信.節點將收集到的數據發送到簇頭節點的過程被稱為簇內通信；簇頭節點將數據轉發到基站則稱為簇間通信.本文采用的節點通信方式具體如下：

1) 簇內通信距離通常小于距離閾值.為了避免傳輸信號出現沖突，簇內通信采取單跳的方式進行通信.

2) 如果簇頭節點與基站之間的距離大于距離閾值，采用單跳的方式會急速消耗網絡能量，此時簇間通信采用多跳的方式將數據轉發到基站；如果簇頭節點與基站之間的距離小于距離閾值，則簇間通信采取直接與基站進行通信的方式.

4 仿真驗證

為了驗證本文提出的路由算法的有效性，采用Matlab對其進行了仿真實驗測試，并與LEACH算法、EECPK-means算法和能量質心算法進行了對比分析，具體的實驗仿真參數見表1.

4.1 簇結構對比分析

根據式(13),在100 m×100 m的區域隨機生成100個節點的位置，第i個節點的橫、縱坐標分別為S(i)·x和S(i)·y，rand()用來生成[0,1]之間均勻分布的隨機數.根據3.1節中的均勻分區方法對監測區域進行分區，再使用能量質心算法和EECPK-means算法對監測區域進行分區，得到三種算法各分區節點數量對比圖，如圖4所示.由圖4可見，本文算法中各區域節點數最為均衡.

圖4 3種算法各分區節點數量對比

(13)

此外，分別對EECPK-means算法、能量質心算法和本文算法進行5輪觀測，并記錄下各簇頭(C1,C2,C3,C4)的標識號，見表2.從表2可以看出:能量質心算法和EECPK-means算法都有一個共同的缺點，即同一個節點會連續多次被選為簇頭節點，導致節點能量快速消耗；而本文算法的各區隨著每輪初始簇頭的變化而發生位置上變化，從而影響簇頭位置的變化，能夠在一定程度上將簇頭能耗分攤給不同節點.

表2 3種算法5輪觀測中簇頭的標識號

4.2 網絡壽命對比分析

分別對LEACH算法、EECPK-means算法、能量質心算法和本文算法進行仿真，得到4種算法網絡壽命與時間的關系，如圖5所示.從圖5中可以看出:本文提出的算法有效地延長了第一個能量耗盡節點的壽命，其主要原因是本文提出的分區方式具有較大的優勢，能夠有效地均衡各區節點的數量，并且在一定程度上分攤簇頭的能耗；并且，當算法運行到第800輪時，本文算法網絡中還有74個節點存活，能量質心算法有48個節點存活，EECPK-means算法有35個節點存活，LEACH算法僅有6個節點存活.可見，本文算法能夠有效地提高網絡的生存周期.

圖5 4種算法網絡生存周期對比

4.3 網絡能量利用率對比分析

WSN是一種以采集傳感數據為目的且能量受限的網絡，所以除了網絡壽命，網絡的能量利用率也是WSN另一重要的性能指標.網絡能量利用率越高，說明算法越節能.網絡的初始能量為50 J，圖6給出了4種算法網絡能耗與基站接收數據包數量之間的關系.從圖6中可以看出，在接收數據包的數量為2 000個時，本文算法消耗8.884 J能量，能量質心算法消耗了12.09 J能量，EECPK-means算法消耗了16.2 J能量，LEACH算法消耗了48.77 J能量.可知，在接收數據包的數量相同時，本文算法消耗的能量最小，能量利用率最高.其主要原因是，本文算法在簇頭的選舉時優先選擇與分區內其他節點之間的距離和最小的節點，從而使網絡能耗最小，并且從圖5中可以看出，在同一時間，本文算法網絡中存活節點的數量也最多.

圖6 4種算法網絡能量利用率對比

5 結論

本文從均衡簇頭負載和優化網絡能耗兩個方面出發，針對分層路由算法中出現的節點過早死亡、簇頭負載不均衡等問題，提出了基于均勻分區的無線傳感器網絡路由算法.首先采用改進的多叉樹遍歷算法隨機選取分布均勻的初始簇頭，從而使每輪產生不同的簇頭，避免了節點連續多次被選為簇頭的現象，在一定程度上分攤了簇頭能耗；然后基于距離權值函數進行分區，均衡了簇頭的負載；最后，通過分析簇頭位置和網絡能耗的關系得到最優簇頭位置，優化了網絡能耗.仿真結果表明：本文提出的算法能有效均衡簇頭負載，避免節點過早死亡，延長網絡的生存周期，同時提高網絡的能量利用率.