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

1  無線傳感器網(wǎng)絡中的聚類問題

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

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

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

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

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

2  圖論聚類算法的實現(xiàn)

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

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

首先,從圖中某個頂點出發(fā)(設為vi)訪問vi,再從vi出發(fā)，依次訪問vi的所有未被訪問的鄰接點，再從這些鄰接點出發(fā)，依次訪問它們的所有未被訪問的鄰接點，如果圖中仍有未被訪問的頂點，則從中選擇一個作為起點，重復上述過程，直到所有頂點均被訪問過為止。

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

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

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

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

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

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

3  算法性能分析

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

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

4  結論

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