無(wú)線傳感器網(wǎng)絡(luò)從出現(xiàn)至今，己經(jīng)從最初的節(jié)點(diǎn)研制、網(wǎng)絡(luò)協(xié)議設(shè)計(jì)，發(fā)展到了智能群體的研究階段，同時(shí)也已成為國(guó)內(nèi)外一項(xiàng)新的IT熱點(diǎn)技術(shù)。該技術(shù)吸引了大量的學(xué)者對(duì)其展開(kāi)多方面的研究,并取得了一些進(jìn)展，包括眾多的節(jié)點(diǎn)平臺(tái)和大量的通信協(xié)議。然而，目前還沒(méi)有形成一套完整的理論和技術(shù)體系來(lái)支撐這一新興領(lǐng)域的發(fā)展,還有眾多的科學(xué)與技術(shù)問(wèn)題尚待突破,這也是信息領(lǐng)域面臨的一項(xiàng)極具有挑戰(zhàn)性的課題。

1  無(wú)線傳感器網(wǎng)絡(luò)中的聚類(lèi)問(wèn)題

由于無(wú)線傳感器網(wǎng)絡(luò)存在能量約束，而減少需要傳輸?shù)臄?shù)據(jù)量能夠有效地節(jié)省節(jié)點(diǎn)能量，因此，在從各個(gè)節(jié)點(diǎn)收集數(shù)據(jù)的過(guò)程中，可以利用節(jié)點(diǎn)的本地計(jì)算與存儲(chǔ)能力對(duì)數(shù)據(jù)進(jìn)行融合處理，去除冗余信息，達(dá)到降低能量消耗的目的。此外，由于節(jié)點(diǎn)易失效,無(wú)線傳感器網(wǎng)絡(luò)同時(shí)也需要采用數(shù)據(jù)融合技術(shù)來(lái)對(duì)多份傳感數(shù)據(jù)進(jìn)行綜合，以達(dá)到提高信息準(zhǔn)確度的目的。

當(dāng)傳感器分布在一個(gè)比較大的區(qū)域，而且數(shù)量也比較大的時(shí)候，傳感器的數(shù)據(jù)如何向融合中心傳遞是一個(gè)需要解決的問(wèn)題。目前比較流行的是采用三層網(wǎng)絡(luò)來(lái)解決，圖1所示是三層分級(jí)傳感器網(wǎng)絡(luò)的結(jié)構(gòu)示意圖。無(wú)論如何，雖然采用三層網(wǎng)絡(luò)結(jié)構(gòu)雖然必須進(jìn)行分簇,但仍然是一種相對(duì)比較合理的處理方式。

 現(xiàn)在通常采用的分簇方法是聚類(lèi)算法。聚類(lèi)是一種眾所周知而且已經(jīng)被廣泛使用的數(shù)據(jù)分析技術(shù)。所謂聚類(lèi),就是將物理或抽象對(duì)象的集合分組成為由類(lèi)似的對(duì)象組成的多個(gè)類(lèi)的過(guò)程?，F(xiàn)在文獻(xiàn)中的大部分算法都是基于單一環(huán)境的，然而，很多應(yīng)用中的數(shù)據(jù)源大都分布在網(wǎng)絡(luò)環(huán)境下,而且在聚類(lèi)前將這些數(shù)據(jù)釆集到一個(gè)中心位置并不是一個(gè)合適的選擇，而通過(guò)無(wú)線通信方式連接的傳感器網(wǎng)絡(luò)就是這樣的環(huán)境,在這里，將數(shù)據(jù)集中起來(lái)進(jìn)行聚類(lèi)非常困難，而且可擴(kuò)展性也不好。這其中的原因有很多，比如無(wú)線傳感器網(wǎng)絡(luò)中有限的通信帶寬以為感知節(jié)點(diǎn)正常運(yùn)行提供能量的電池能源很有限；無(wú)線傳感器網(wǎng)絡(luò)是以AdHoc方式進(jìn)行通信的，只允許相鄰的感知節(jié)點(diǎn)之間進(jìn)行通信。這就需要數(shù)據(jù)分析算法也要以同樣的方式進(jìn)行通信，目前，這樣的聚類(lèi)算法還沒(méi)有。

通常,聚類(lèi)技術(shù)包括以下幾類(lèi)：劃分方法(Parti-tioningmethod)、層次方法(Hierarchicalmethod)、基于密度的方法(Density-basedmethod)，基于網(wǎng)格的方法(Grid-basedmethod)和基于模型的方法(Model-basedmethod)。這些方法應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)中，都沒(méi)有考慮到節(jié)點(diǎn)布局的復(fù)雜性，所以效果都不是非常理想。

本文以傳感器網(wǎng)絡(luò)節(jié)點(diǎn)布局為復(fù)雜的圖結(jié)構(gòu)，提出采用圖論的方法來(lái)選擇合理的節(jié)點(diǎn)作為簇，以達(dá)到花費(fèi)最小能量代價(jià)，完成信息到融合中心的傳遞的目的。其具體算法框圖如圖2所示。 

2  圖論聚類(lèi)算法的實(shí)現(xiàn)

2.1  圖廣度優(yōu)先搜索算法

根據(jù)節(jié)點(diǎn)的總數(shù)目N和需要分成的簇?cái)?shù)M,便可以得到每個(gè)簇的節(jié)點(diǎn)數(shù)為N/M,在整個(gè)圖的廣度優(yōu)先搜索的過(guò)程中，記錄下搜索的節(jié)點(diǎn)數(shù)，達(dá)到N/M后記所有節(jié)點(diǎn)，并將累計(jì)節(jié)點(diǎn)數(shù)重新清零，直至整個(gè)圖完全遍歷完，這樣就可以將相鄰的節(jié)點(diǎn)分成M個(gè)子圖，每個(gè)子圖為一個(gè)簇。其圖廣度優(yōu)先搜索算法的具體過(guò)程如下：

首先,從圖中某個(gè)頂點(diǎn)出發(fā)(設(shè)為vi)訪問(wèn)vi,再?gòu)膙i出發(fā)，依次訪問(wèn)vi的所有未被訪問(wèn)的鄰接點(diǎn)，再?gòu)倪@些鄰接點(diǎn)出發(fā)，依次訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn)，如果圖中仍有未被訪問(wèn)的頂點(diǎn)，則從中選擇一個(gè)作為起點(diǎn)，重復(fù)上述過(guò)程，直到所有頂點(diǎn)均被訪問(wèn)過(guò)為止。

2.2  廣度優(yōu)先搜索算法的VC＋＋實(shí)現(xiàn)屋

廣度優(yōu)先搜索算法的VC＋＋實(shí)現(xiàn)代碼如下：

2.3  簇內(nèi)節(jié)點(diǎn)信息傳遞的最優(yōu)路徑實(shí)現(xiàn)

對(duì)于簇內(nèi)的信息傳遞，其目標(biāo)也是用最小的能量代價(jià)將信息傳給簇頭，本文選擇普里姆算法來(lái)實(shí)現(xiàn)簇子圖的最優(yōu)構(gòu)造。普里姆算法是圖的最小生成樹(shù)的一種構(gòu)造算法。

假設(shè)W_N=(V,{E})是一個(gè)含有N個(gè)頂點(diǎn)的連通網(wǎng)，T_v是W_N上最小生成樹(shù)中頂點(diǎn)的集合，T_E是最小生成樹(shù)中邊的集合。顯然，在算法執(zhí)行結(jié)束時(shí)，Tv=V,而T_E是E的一個(gè)子集。在算法開(kāi)始執(zhí)行時(shí)，T_E為空集，Tv中只有一個(gè)頂點(diǎn)，因此，按普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程是：在所有“其一個(gè)頂點(diǎn)已經(jīng)落在生成樹(shù)上，而另一個(gè)頂點(diǎn)尚未落在生成樹(shù)上”的邊中取一條權(quán)值為最小的邊，并逐條加在生成樹(shù)上，直至生成樹(shù)中含有N-1條邊為止。

找出子圖的最小生成樹(shù)后,可選擇直接連接節(jié)點(diǎn)最多的節(jié)點(diǎn)作為簇頭，其他節(jié)點(diǎn)的信息則間接或直接傳給簇頭，最后由簇頭傳給數(shù)據(jù)融合中心。

3  算法性能分析

本文在一臺(tái)PC機(jī)上用VC++6.0編程環(huán)境實(shí)現(xiàn)了該算法，其機(jī)器配置為Windows XP professional操作系統(tǒng)，1GHz內(nèi)存，120GHz硬盤(pán)，CPU主頻為2.0GHz。本文用多線程工作方式來(lái)模擬無(wú)線傳感器網(wǎng)絡(luò)的工作環(huán)境。仿真過(guò)程中，將無(wú)線傳感器網(wǎng)絡(luò)基于圖論的分布式聚類(lèi)算法(上面的線條)與將所有數(shù)據(jù)傳回sink節(jié)點(diǎn)進(jìn)行計(jì)算的集中式K-平均算法(下面的線條)在性能上進(jìn)行了比較，最后給出了隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的增加，算法執(zhí)行時(shí)間的變化情況。圖3所示是圖論分布式聚類(lèi)算法與集中式K-平均算法的性能比較曲線。

圖3中，橫坐標(biāo)為節(jié)點(diǎn)數(shù)目，縱坐標(biāo)為時(shí)間(單位為s)，從該仿真實(shí)驗(yàn)中可以明顯看出，其圖論分布式聚類(lèi)算法比集中式K-平均算法的性能要優(yōu)越。 

4  結(jié)論

基于圖論的分布式聚類(lèi)算法與將所有數(shù)據(jù)傳回sinK節(jié)點(diǎn)進(jìn)行計(jì)算的集中式K-平均算法在性能相比有較大提高，聚類(lèi)算法的使用可以降低無(wú)線傳感器網(wǎng)絡(luò)在信息傳遞過(guò)程中的能量消耗。下一步的工作將改進(jìn)簇內(nèi)部信息傳遞的方式,進(jìn)一步降低信息傳遞過(guò)程中的能量消耗。