0 引 言

經(jīng)典的復雜網(wǎng)絡理論已經(jīng)證明： 小世界效應 在社會關系網(wǎng)絡中廣泛存在[1,2]。小世界現(xiàn)象的本質特征是具有小的平均路徑長度和大的集聚系數(shù) [3,4]。小世界特征普遍存在于如計算機互聯(lián)網(wǎng)、科學家合作網(wǎng)、社會關系網(wǎng)等現(xiàn)實網(wǎng)絡中，同時小世界理論還廣泛存在于電力網(wǎng)絡、神經(jīng)網(wǎng)絡等系統(tǒng)中[5,6]。真實的網(wǎng)絡可以分為關系網(wǎng)絡與空間網(wǎng)絡兩大類。在關系網(wǎng)絡（Relation Network）的拓撲結構中，節(jié)點之間的連接與節(jié)點距離和位置無關，節(jié)點之間的距離以跳數(shù)來計算；空間網(wǎng)絡（Spatial Network）節(jié)點之間的連接與節(jié)點之間的距離和位置緊密相關。傳統(tǒng)的復雜網(wǎng)絡研究通常都將社會關系或者技術網(wǎng)絡抽象為關系網(wǎng)絡，屬于關系圖的范疇 ；無線 Ad-Hoc 網(wǎng)絡與無線傳感器網(wǎng)絡由于其傳輸半徑的限制，是空間網(wǎng)絡，屬于空間圖的范疇?？臻g網(wǎng)絡的拓撲結構與連通性及傳輸半徑緊密相關。

小世界特征是指網(wǎng)絡較小的平均路徑長度和大的聚類系數(shù)，無線傳感網(wǎng)絡中節(jié)點之間采用無線多跳方式傳輸數(shù)據(jù)，引入小世界特征可以降低網(wǎng)絡系統(tǒng)的通信開銷，并增強網(wǎng)絡的容錯性，從而延長整個系統(tǒng)的生存時間[7-11]。張 [12] 等選擇性地刪除一些邊，基于匯聚節(jié)點建立捷徑，交替進行，直到兩個小世界特征達到最優(yōu)。周[13] 等基于小世界與能效提出了一種容遲網(wǎng)絡路由算法。Nardis[14] 等設計了一種自適應選舉簇頭，簇頭之間動態(tài)建立捷徑，生成具有小世界特征的網(wǎng)絡拓撲結構， 實驗結果顯示了該網(wǎng)絡的優(yōu)良性能。

根據(jù)傳感網(wǎng)應用環(huán)境的不同，部署方式可以分為確定性部署和隨機部署兩類。在監(jiān)測范圍小且人類方便到達的應用環(huán)境如車間、醫(yī)院、商場中，可以預先確定傳感器節(jié)點的位置并手工部署在確定位置上。但當網(wǎng)絡規(guī)模較大或在環(huán)境惡劣危險的場合應用時，如湖泊、沼澤、沙漠、戰(zhàn)場、疫區(qū)等，通常采用隨機播撒方式。本文在無線傳感網(wǎng)中引入復雜網(wǎng)絡中的小世界特征，結合確定性部署和隨機部署方式，在隨機部署的基礎上，確定部署少量具有更高能量、更強數(shù)據(jù)處理能力的超級節(jié)點，在超級節(jié)點和匯聚節(jié)點之間建立超級鏈路形成直接通信的可靠捷徑，從而構建基于無線傳感器網(wǎng)絡小世界效應的網(wǎng)絡模型。

1 小世界效應的傳感器網(wǎng)絡模型

1.1 網(wǎng)絡模型設計

在無線傳感網(wǎng)絡應用中，通常傳感器節(jié)點一旦部署，位置便相對固定，且需長期運行監(jiān)測如森林火災檢測的應用場景， 本文采用的網(wǎng)絡模型為 N個傳感器節(jié)點均勻部署在一個 XY 的長方形區(qū)域 Z內(nèi)，每個節(jié)點均勻分布在交叉點上，為了避免網(wǎng)絡拓撲結構經(jīng)常改變，假定所有傳感器節(jié)點一旦部署位置固定，且這些節(jié)點是同構的，具有相同的能量和相同的通信半徑， 并知道自己的位置信息，位置采用平面坐標（x，y）標記，其中 0 ≤ x≤ X－ 1，0 ≤ y≤ Y－ 1。網(wǎng)絡拓撲形成平面 Mesh結構，如圖 1所示。

圖1 加入超級節(jié)點后的傳感器網(wǎng)絡

傳感器節(jié)點只與臨近節(jié)點即與自己垂直和水平方向的節(jié)點傳送和接收數(shù)據(jù)，匯聚節(jié)點可以部署于區(qū)域范圍內(nèi)的任何位置，傳感器節(jié)點以一定的速率發(fā)送數(shù)據(jù)傳到匯聚節(jié)點，匯聚節(jié)點可以與其他有線網(wǎng)絡或者無線網(wǎng)絡連接，最后傳送到用戶終端。傳感器節(jié)點也可采用貪婪路由策略，即數(shù)據(jù)經(jīng)最短距離傳送到匯聚節(jié)點。

1.2 小世界效應分析

假設已知普通節(jié)點 Ni的平面坐標位置為（xi，yi），普通節(jié)點 N位于（x，y），匯聚節(jié)點 Sink 的平面坐標位置為（x，y）。先計算普通節(jié)點 Ni 和 Nj 不經(jīng)過超級節(jié)點把數(shù)據(jù)發(fā)送給匯聚節(jié)點的最短跳數(shù)距離為：

當H（Ni，S）≥ H' （Ni，S）時，節(jié)點選擇經(jīng)超級節(jié)點發(fā)送數(shù)據(jù)。 反之，當 H（Nj，S）<H'（Nj，S），即普通節(jié)點 Nj 離匯聚節(jié)點較 近時，節(jié)點 Nj 經(jīng)其他普通節(jié)點無線多跳到達匯聚節(jié)點。

小世界網(wǎng)絡具有較小的特征路徑長度。在一般復雜網(wǎng)絡 中，特征路徑長度指網(wǎng)絡中任意兩點之間最短路徑的平均值。 在無線傳感網(wǎng)絡中，所有傳感器節(jié)點感知的數(shù)據(jù)均向匯聚節(jié)點 匯集，傳送數(shù)據(jù)具有明確的方向性，數(shù)據(jù)流向是一種“多對一” 的集中匯聚模式，在本節(jié)仿真分析中給匯聚節(jié)點設定了特定的 地理位置，所以平均路徑長度需要根據(jù)傳感器網(wǎng)絡的特殊性 進行修正。這里的平均路徑長度APL 指為傳感網(wǎng)絡中所有節(jié) 點發(fā)送數(shù)據(jù)到達匯聚節(jié)點所經(jīng)過的通信跳數(shù)平均值，表示為：

所以，在同構 Mesh 網(wǎng)絡與通過增設 μ 個超級節(jié)點而構 造生成的超級鏈路網(wǎng)絡之間，網(wǎng)絡節(jié)點到超級節(jié)點或匯聚節(jié)點 的平均路徑長度的比率定義為平均路徑長度的變化率，記為：

能量節(jié)省比率越大，表示傳感器網(wǎng)絡的能量效率越高。

對于增設了超級節(jié)點后的無線傳感器網(wǎng)絡，超級節(jié)點周圍 的普通節(jié)點通過超級節(jié)點發(fā)送數(shù)據(jù)，網(wǎng)絡拓撲發(fā)生相應變化， 網(wǎng)絡出現(xiàn)聚類特性，可認為具有較高的聚類系數(shù)。

1.3 仿真結果

仿真實驗采用規(guī)模為 20×20 的 Mesh 網(wǎng)絡，普通節(jié)點部 署在 Mesh 網(wǎng)絡中的交叉點上，匯聚節(jié)點分別部署在（0，0） 和網(wǎng)絡的中心（10，10）位置，假設超級節(jié)點同樣均勻部署在 監(jiān)測環(huán)境中，如圖 2 所示。

平均路徑長度（APL）與超級節(jié)點的關系如圖 3 所示，展 示了網(wǎng)絡中超級節(jié)點數(shù)和平均路徑長度APL（μ）之間的關系。 圖中顯示了添加網(wǎng)絡中的部分超級節(jié)點，超級節(jié)點的網(wǎng)絡節(jié)點 的平均路徑長度迅速下降，尤其在匯聚節(jié)點處（0，0）比（10， 10）提高更為顯著，當匯聚節(jié)點處在（0，0）的位置時，超級 節(jié)點增加 1～ 6 個，平均路徑長度由10 降至 4。然而，當超級 節(jié)點繼續(xù)增加時，平均路徑長度下降非常緩慢。結果表明，在 同構網(wǎng)絡中加入少量超級節(jié)點，平均路徑長度迅速下降，網(wǎng)絡 具有小世界特征。

平均路徑長度變化率 APLR（μ）與超級節(jié)點數(shù)的關系如 圖 4 所示。在兩個模擬環(huán)境中都添加了6 個超級節(jié)點，網(wǎng)絡的 平均路徑長度減少約至 45%。由曲線可知，若繼續(xù)增加超級節(jié) 點的數(shù)量，路徑長度將不再顯著減少。因此，合理增加超級節(jié) 點對網(wǎng)絡拓撲結構沒有太大影響，但可以大大減少數(shù)據(jù)傳輸 的網(wǎng)絡路徑長度，進一步體現(xiàn)了小世界復雜網(wǎng)絡的特點。

網(wǎng)絡節(jié)能比率與增設超級節(jié)點的關系如圖 5 所示。當增 加第 1～ 6 條超級鏈路時，網(wǎng)絡節(jié)能比率約 50%，但增加更 多超級鏈路后節(jié)能效果不明顯。且當匯聚節(jié)點位于（0，0）時， 比位于（10，10）時節(jié)能效果有明顯提高。

2 結 語

本文首先分析了小世界效應在無線傳感器網(wǎng)絡中的應用 和研究。在無線傳感網(wǎng)絡中，引入超級節(jié)點和超級鏈路，提出 了小世界特征的網(wǎng)絡模型，仿真分析了超級節(jié)點數(shù)對網(wǎng)絡平均 路徑長度、路徑長度變化率和網(wǎng)絡節(jié)能率的影響，增加少量 超級節(jié)點可以減少網(wǎng)絡數(shù)據(jù)傳輸延遲，提高網(wǎng)絡的能量效率。 本文考慮的是節(jié)點均勻分布在 Mesh 網(wǎng)絡的交叉點上，針對無 線傳感器網(wǎng)絡隨機分布節(jié)點的情況，增設超級節(jié)點的節(jié)能問題 還須進一步討論。