基于無(wú)線傳感器網(wǎng)絡(luò)的K均值算法研究

石紅麗， 王 潔 ， 唐 艷， 張小軍

（1.成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610059；2.長(zhǎng)慶油田超低滲透油藏第一項(xiàng)目部 甘肅 慶陽(yáng) 745400）

無(wú)線傳感網(wǎng)是計(jì)算機(jī)技術(shù)應(yīng)用的一個(gè)嶄新研究領(lǐng)域，它綜合了傳感器技術(shù)、嵌入式計(jì)算技術(shù)、分布式信息處理技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無(wú)線通信等技術(shù)。通過(guò)各類微型傳感器對(duì)目標(biāo)信息進(jìn)行實(shí)時(shí)監(jiān)測(cè)，由嵌入式計(jì)算資源對(duì)信息進(jìn)行處理，能夠協(xié)作地實(shí)時(shí)監(jiān)測(cè)、感知和采集各種環(huán)境信息。在軍事國(guó)防、工農(nóng)業(yè)控制、城市管理、生物醫(yī)療、環(huán)境監(jiān)測(cè)、搶險(xiǎn)救災(zāi)、防恐反恐和危險(xiǎn)遠(yuǎn)程控制等許多領(lǐng)域都有重要的科研和實(shí)用價(jià)值。目前，對(duì)無(wú)線傳感器網(wǎng)絡(luò)的研究主要集中在網(wǎng)絡(luò)層和鏈路層，而路由算法已成為無(wú)線傳感器網(wǎng)絡(luò)的核心技術(shù)之一。根據(jù)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的地位和功能是否相同，路由算法可以分成平面路由算法和分簇路由算法。K均值算法是一種比較成熟的基于聚類的算法，選擇K均值算法作為探討的對(duì)象具有較好的意義和研究前景。

1 傳感器網(wǎng)絡(luò)結(jié)構(gòu)

傳感器網(wǎng)絡(luò)[1]結(jié)構(gòu)如圖1所示，通常包括傳感器節(jié)點(diǎn)（sensor node）、匯聚節(jié)點(diǎn)（sink node）和管理節(jié)點(diǎn)。大量傳感器節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域 （sensor field）并通過(guò)自組織方式構(gòu)成網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)監(jiān)測(cè)的數(shù)據(jù)經(jīng)過(guò)多跳后路由到匯聚節(jié)點(diǎn)[2]，最后通過(guò)互聯(lián)網(wǎng)或衛(wèi)星到達(dá)管理節(jié)點(diǎn)。用戶通過(guò)管理節(jié)點(diǎn)對(duì)傳感器網(wǎng)絡(luò)進(jìn)行配置和管理，發(fā)布監(jiān)測(cè)任務(wù)以及收集監(jiān)測(cè)數(shù)據(jù)。傳感器節(jié)點(diǎn)能量有限，處理能力、存儲(chǔ)能力和通信能力相對(duì)較弱。它們主要是進(jìn)行本地信息收集和數(shù)據(jù)處理外，并且對(duì)轉(zhuǎn)發(fā)來(lái)的數(shù)據(jù)進(jìn)行處理。

由于無(wú)線傳感器網(wǎng)絡(luò)自身的特點(diǎn)，要求其路由協(xié)議必須能夠滿足相應(yīng)的應(yīng)用要求、可以實(shí)現(xiàn)較低的網(wǎng)絡(luò)消耗、整體有效地利用資源以及擁有較高的網(wǎng)絡(luò)吞吐量，這就要求無(wú)線傳感器網(wǎng)絡(luò)的路由不能像傳統(tǒng)的網(wǎng)絡(luò)一樣，因此，它具有傳統(tǒng)網(wǎng)絡(luò)所不具備的一些特點(diǎn)：1）具有應(yīng)用相關(guān)性；2）均衡性低耗能；3）以數(shù)據(jù)為中心。

由此可見(jiàn)能耗問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)的關(guān)鍵問(wèn)題之一。層次路由協(xié)議已經(jīng)被證明能夠有效地節(jié)約能量，它將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)劃分為簇頭節(jié)點(diǎn)和一般節(jié)點(diǎn)兩類。 一般節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的采集，并將采集到得數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)。簇頭節(jié)點(diǎn)接收簇內(nèi)一般節(jié)點(diǎn)發(fā)來(lái)的數(shù)據(jù)，融合后再轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)，這種算法稱為分簇算法。具有代表性的分簇算法有LEACH[3]、PEGAGIS、HEED等。在不改變硬件的前提下，通過(guò)深入分析這些代表性的算法存在的不足，提出了一種基于聚類的K均值算法。

2 K均值算法原理

2.1 K均值算法的前提

K均值算法[4-5]基于如下前提：

1）無(wú)線傳感器網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的位置已定；

2）每個(gè)節(jié)點(diǎn)包括簇頭節(jié)點(diǎn)是靜止的；

3）每個(gè)節(jié)點(diǎn)的通信半徑可調(diào)，并可以與簇頭節(jié)點(diǎn)直接通信；4）整個(gè)網(wǎng)絡(luò)的簇頭個(gè)數(shù)是固定的。

2.2 算法的具體思想

K均值[6]是一種迭代的聚類算法，迭代過(guò)程中不斷地移動(dòng)簇集中的成員，直到得到理想的簇集為主，在這里理想的簇集標(biāo)準(zhǔn)為具有低能耗、高穩(wěn)定性[7-8]。

K均值偽代碼：

2.3 K的確定方式

K的確定方式如下：

I為網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)，εfs為自由空間衰減信道模式（d2功耗）放大指數(shù)，εmp為多路徑衰減信道模式（d4功耗）放大指數(shù)，dtoBs為簇頭節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離，J為正方形區(qū)域邊長(zhǎng)。

利用無(wú)線電通信模型[9-10]用ETx/ERx分別表示節(jié)點(diǎn)發(fā)送/接收信息消耗的能量，則節(jié)點(diǎn)經(jīng)過(guò)距離d發(fā)送k比特?cái)?shù)據(jù)消耗的能量為：

節(jié)點(diǎn)接收k比特?cái)?shù)據(jù)消耗的能能量為：

無(wú)線電通信模型如圖2所示。

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

100個(gè)節(jié)點(diǎn)m分布在100×100的矩陣區(qū)域中，各樣本節(jié)點(diǎn)位于（0，100）處，整個(gè)網(wǎng)絡(luò)被分為5個(gè)區(qū)域，即為5個(gè)分簇。 初始能量 Einit=1 J ， Eelec=25 nJ/bit，εmp=5 pJ/bit/m2，數(shù)據(jù)融合所消耗的能量EDA=25 pJ/bit/singnal，每次內(nèi)部節(jié)點(diǎn)要發(fā)送的數(shù)據(jù)大小為1 000 bit.

樣本點(diǎn)的坐標(biāo)：

100個(gè)節(jié)點(diǎn)分布情況如圖3所示。100個(gè)節(jié)點(diǎn)分布情況聚類后的情況如圖4所示。

分成五類后的簇頭節(jié)點(diǎn)坐標(biāo)：

C=[45 53；46 5；49 82；73 70；18 89]

將以上數(shù)據(jù)通過(guò)NS-2仿真平臺(tái)仿真，發(fā)現(xiàn)K均值算法第一個(gè)節(jié)點(diǎn)的死亡時(shí)間 （FND）和全部節(jié)點(diǎn)死亡的時(shí)間（LND）都比LEACH[3]算法的時(shí)間長(zhǎng)。統(tǒng)計(jì)50次實(shí)驗(yàn)后的結(jié)果為:K均值算法的FND平均是LEACH的115倍，LND平均是LEACH的117倍。這說(shuō)明本文的算法將能量的損耗均勻分布到了所有節(jié)點(diǎn)中，避免了單個(gè)節(jié)點(diǎn)過(guò)早死亡，提高了網(wǎng)絡(luò)的生命周期。

4 結(jié)束語(yǔ)

本文提出了一種基于無(wú)線傳感器網(wǎng)絡(luò)的K均值算法，它生成的簇頭節(jié)點(diǎn)散播到了網(wǎng)絡(luò)的各個(gè)區(qū)域中，從而減少了每個(gè)區(qū)域內(nèi)通信的能耗和可能會(huì)出現(xiàn)的節(jié)點(diǎn)稀疏沒(méi)有簇頭節(jié)點(diǎn)而導(dǎo)致一般節(jié)點(diǎn)直接與匯聚節(jié)點(diǎn)通信導(dǎo)致過(guò)早死亡的情況，從而避免了網(wǎng)絡(luò)對(duì)該區(qū)域提早失去監(jiān)控。本算法對(duì)各節(jié)點(diǎn)位置確定的無(wú)線傳感器網(wǎng)絡(luò)有低能耗、高穩(wěn)定性。由于現(xiàn)階段還處于模擬仿真階段，還不能將已有算法寫(xiě)入平臺(tái)中達(dá)到自適應(yīng)的階段。

[1]楊冕，秦前清.基于無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議[J].計(jì)算機(jī)工程與應(yīng)用， 2004（32）:130-131.YANG Mian，QINQian-qing.Routingprotocolbasedonwireless sensor network[J].Computer Engineering and Applications，2004（32）:130-131.

[2]Dunham M H.數(shù)據(jù)挖掘教程[M].北京:清華大學(xué)出版社，2005:95-131.

[3]唐漪.無(wú)線傳感器網(wǎng)絡(luò)LEACH算法的研究與改進(jìn)[D].蘭州:蘭州理工大學(xué)，2008.

[4]陳良維.數(shù)據(jù)挖掘中聚類算法研究[J].微計(jì)算機(jī)信息，2006，2（1）:209-211.CHEN Liang-wei.Clustering algorithm study in data mining[J].Journal of Micro Computer Information，2006，2（1）:209-211.

[5]楊小兵.聚類分析中若干關(guān)鍵技術(shù)的研究[D].杭州:浙江大學(xué)計(jì)算機(jī)學(xué)院，2005.

[6]Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy efficient communication protocol for wireless microsensor networks [C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences， 2000（2）：10.

[7]Lindsey S，Raghavendra C S.PEGASIS:power efficient gathering in sensor information systems[C]//Proceedings of IEEE Aerospace Conference，2002（3）:1125-1130.

[8]徐義峰，陳春明，徐云青.一種改進(jìn)的k均值聚類算法[J].計(jì)算機(jī)應(yīng)用與軟件，2008，25（3）:275-277.XU Yi-feng， CHEN Chun-ming， XU Yun-qing.An improved clustering algorithm for K-means[J].Computer Applications and Software， 2008， 25（3）:275-277.

[9]顧洪博，張繼懷.基于孤立點(diǎn)和初始質(zhì)心選擇的K-均值算法改進(jìn)[J].長(zhǎng)江大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，6（1）:60-62.GU Hong-bo，ZHANG Ji-huai.Animproved K-means algorithm based on outliers and original clustering center[J].Journal of Yangtze University：Natural Science， 2009，6（1）:60-62.

[10]徐藝萍.動(dòng)態(tài)聚類法研究[D].重慶:西南大學(xué)，2006.