無(wú)線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂?/h1>
2008-12-31 00:00:00卞永釗于海斌曾鵬
計(jì)算機(jī)應(yīng)用研究 2008年10期
收稿日期：2008-01-16；
修回日期：2008-03-24
基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(60704046 60725312)；遼寧省工業(yè)通信與控制系統(tǒng)重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目
作者簡(jiǎn)介：卞永釗（1976-），男，博士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)管理、拓?fù)淇刂?bian_yz@sia.cn)；
于海斌（1964-），男，研究員，博導(dǎo)，主要研究方向?yàn)橹悄芸刂葡到y(tǒng)、網(wǎng)絡(luò)化技術(shù)等;
曾鵬（1976-），男，研究員，碩導(dǎo)，主要研究方向?yàn)閰f(xié)議工程、無(wú)線傳感器網(wǎng)絡(luò).
(1.中國(guó)科學(xué)院 沈陽(yáng)自動(dòng)化所 沈陽(yáng)110016; 2.中國(guó)科學(xué)院 研究生院 北京100039)
摘要：拓?fù)淇刂剖菬o(wú)線傳感器網(wǎng)絡(luò)研究中的核心問(wèn)題之一，它對(duì)于提高網(wǎng)絡(luò)生存周期、降低通信干擾、提高M(jìn)AC和路由協(xié)議、保證網(wǎng)絡(luò)連通和覆蓋質(zhì)量、提高網(wǎng)絡(luò)服務(wù)等具有重要意義。闡述了拓?fù)淇刂萍夹g(shù)研究的進(jìn)展，首先描述了拓?fù)淇刂萍捌浞椒ā⒃u(píng)價(jià)標(biāo)準(zhǔn)，然后從平面網(wǎng)絡(luò)、層次型網(wǎng)絡(luò)拓?fù)淇刂平榻B了一些代表性的研究工作，并指出了這些工作存在的不足，最后總結(jié)了研究現(xiàn)狀中存在的問(wèn)題以及拓?fù)淇刂蒲芯康陌l(fā)展方向。
關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò); 拓?fù)淇刂疲?功率控制； 支配集； 成簇算法
中圖分類(lèi)號(hào)：TP309
文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：1001-3695(2008)10-3128-06
Topology control for wireless sensor networks
BIAN Yong-zhao1，2 YU Hai-bin ZENG Peng1
(1.Shenyang Institute of Automation Chinese Academy of Sciences Shenyang 110016 China;
2.Graduate School Chinese Academy of-Sciences Beijing 100039 China)
Abstract:Topology control is one of the fundamental problems in wireless sensor networks. It is of great importance for prolonging network lifetime reducing radio interference increasing the efficiency of MAC and routing protocols ensure the-qua-lity of connecting and coverage increasing the network services and so on. This paper described the topology control problem and its methods criterion of estimation firstly then made an introduction of representative research efforts from two aspects homogeneous and non-homogeneous networks respectively and pointed out the defects of those efforts. Finally summarized existing problems open issues and research trends.
Key words：wirelss sensor networks(WSN); topology control; transmit power control; dominating set; clustering algorithm
0引言
無(wú)線傳感器網(wǎng)絡(luò)是一種新興的網(wǎng)絡(luò)，一般具有大規(guī)模、自組織、隨機(jī)部署、環(huán)境復(fù)雜、傳感器節(jié)點(diǎn)資源有限、網(wǎng)絡(luò)拓?fù)浣?jīng)常發(fā)生變化的特點(diǎn)[1]。無(wú)線傳感器網(wǎng)絡(luò)的這些特點(diǎn)決定了拓?fù)淇刂圃跓o(wú)線傳感器網(wǎng)絡(luò)研究中的重要作用，同時(shí)這些特點(diǎn)也使得它的拓?fù)淇刂蒲芯烤哂刑魬?zhàn)性。首先，拓?fù)淇刂剖且环N重要的節(jié)能技術(shù)；其次，拓?fù)淇刂票ＷC網(wǎng)絡(luò)覆蓋的質(zhì)量和連通質(zhì)量；另外拓?fù)淇刂颇軌蚪档屯ㄐ鸥蓴_、提高M(jìn)AC協(xié)議和路由協(xié)議的效率，為數(shù)據(jù)融合提供拓?fù)浠A(chǔ)；拓?fù)淇刂颇軌蛱岣呔W(wǎng)絡(luò)的容量、可靠性、可擴(kuò)展性等其他性能。總之拓?fù)淇刂茖?duì)網(wǎng)絡(luò)性能具有重大的影響，因而對(duì)它研究具有十分重要的意義。
本文提到的拓?fù)淇刂剖侵缚刂凭W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)由活動(dòng)節(jié)點(diǎn)的子集和進(jìn)行直接通信的活動(dòng)鏈路決定。拓?fù)淇刂扑惴ㄒ詧DG=(V，E)代表網(wǎng)絡(luò)。其中：V是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，當(dāng)且僅當(dāng)v1與v2之間有直接通信時(shí)，邊(v1，v2)∈EV2存在，將它變換到圖T＝(VT，ET)，可以得到VT∈V，ET∈E。
圖G代表原始網(wǎng)絡(luò)，為了能從圖G計(jì)算出變化后的圖T，拓?fù)淇刂扑惴ㄓ幸韵聨追N常用的方法：
a)減少活動(dòng)節(jié)點(diǎn)的數(shù)量(VTV)。例如可以利用網(wǎng)絡(luò)的冗余部署特性，周期性地關(guān)閉剩余能量較少的節(jié)點(diǎn)，激活其他節(jié)點(diǎn)來(lái)代替被關(guān)閉的節(jié)點(diǎn)。
b)可以控制活動(dòng)鏈路集或鄰節(jié)點(diǎn)集。如果無(wú)須使用網(wǎng)絡(luò)中的所有鏈路，那么可以剔除一些鏈路，將通信限制在重要鏈路中。
如果網(wǎng)絡(luò)是同構(gòu)的，即平面網(wǎng)絡(luò)，控制節(jié)點(diǎn)的鄰節(jié)點(diǎn)集只需不與某些節(jié)點(diǎn)通信即可。在無(wú)線傳感器網(wǎng)絡(luò)中選擇鄰節(jié)點(diǎn)最適合的方法就是控制節(jié)點(diǎn)的信號(hào)發(fā)射范圍，也就是采用功率控制或者采用自適應(yīng)的功率調(diào)整方法。圖1和2給出了原始的網(wǎng)絡(luò)拓?fù)浜凸β士刂浦蟮耐負(fù)浣Y(jié)構(gòu)。
拓?fù)淇刂埔部梢圆捎玫诙N方法，即重新安排活動(dòng)鏈路或鄰節(jié)點(diǎn)，形成一個(gè)層次型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并假設(shè)處于上層的節(jié)點(diǎn)具有特殊的功能。
如選擇某些節(jié)點(diǎn)作為骨干節(jié)點(diǎn)，只保持骨干節(jié)點(diǎn)之間的連接，其他節(jié)點(diǎn)的連接都指向骨干節(jié)點(diǎn)，所以骨干節(jié)點(diǎn)就形成了一個(gè)支配集(dominating set)：子集DV，V中的所有節(jié)點(diǎn)要么在D中，要么是節(jié)點(diǎn)d∈D的單跳鄰節(jié)點(diǎn)(v∈V:v∈D∨d∈D:(v，d)∈E)。支配集節(jié)點(diǎn)之間相互通信以及支配集與其鄰節(jié)點(diǎn)之間可以進(jìn)行通信，這樣能夠保證網(wǎng)絡(luò)的連通性。
另一種與支配集相關(guān)但略有不同的思想就是將網(wǎng)絡(luò)劃分成簇(clusters)。簇是包括原始網(wǎng)絡(luò)中所有節(jié)點(diǎn)的節(jié)點(diǎn)集的子集，每個(gè)簇中有簇首(cluster heads)，它是簇的代表，每個(gè)簇內(nèi)的節(jié)點(diǎn)距離簇首一般只有一跳。如果使簇的數(shù)量最小，就相當(dāng)于尋找最大獨(dú)立集(independent set)(存在子集CV，使v∈V-C:c∈C:(v，c)∈E，且C中沒(méi)有兩個(gè)節(jié)點(diǎn)在邊E-c1，c2∈C:(c1，c2)E上相交)。在這樣的分簇型的網(wǎng)絡(luò)中，簇首負(fù)責(zé)與簇內(nèi)節(jié)點(diǎn)之間的通信，同時(shí)簇間連接也是通過(guò)簇首的通信來(lái)實(shí)現(xiàn)的，這樣就可以保證整個(gè)網(wǎng)絡(luò)的連通性。圖3和4給出了采用骨干節(jié)點(diǎn)控制和簇結(jié)構(gòu)控制之后的拓?fù)浣Y(jié)構(gòu)。
1拓?fù)淇刂频脑u(píng)價(jià)標(biāo)準(zhǔn)
拓?fù)淇刂埔ＷC在一定的網(wǎng)絡(luò)連通質(zhì)量和覆蓋質(zhì)量的前提下，一般以延長(zhǎng)網(wǎng)絡(luò)生存周期為主要目標(biāo)，兼顧通信干擾、網(wǎng)絡(luò)延遲、負(fù)載均衡、可靠性、可擴(kuò)展性等其他性能，形成一個(gè)優(yōu)化的拓?fù)浣Y(jié)構(gòu)。無(wú)線傳感器網(wǎng)絡(luò)是與應(yīng)用相關(guān)的，不同的應(yīng)用其設(shè)計(jì)目標(biāo)不盡相同，采用的拓?fù)浣Y(jié)構(gòu)控制手段也不盡相同。以下提出一般拓?fù)淇刂扑惴ǖ膸讉€(gè)評(píng)價(jià)指標(biāo)。
1)連通性拓?fù)淇刂撇荒苁惯B通圖G變成非連通圖。也就是說(shuō)，如果G中的節(jié)點(diǎn)u與v之間有一條(可能是多跳)路徑，那么在T中也應(yīng)該有這樣一條路徑(顯然，不一定是同一條路徑)。如果至少要去掉k個(gè)節(jié)點(diǎn)才能使網(wǎng)絡(luò)不連通，那么就稱網(wǎng)絡(luò)是k-連通的，或者網(wǎng)絡(luò)的連通度為k。拓?fù)淇刂埔ＷC網(wǎng)絡(luò)是連通的(即至少1-連通)，這是拓?fù)淇刂频幕疽蟆＊?/p>
2）覆蓋率覆蓋率可以看成是對(duì)傳感器服務(wù)質(zhì)量的度量。覆蓋問(wèn)題可以分為區(qū)域覆蓋、點(diǎn)覆蓋和柵欄覆蓋[2]。區(qū)域覆蓋研究對(duì)目標(biāo)區(qū)域的覆蓋(監(jiān)測(cè))問(wèn)題；點(diǎn)覆蓋研究對(duì)一些離散的目標(biāo)點(diǎn)的覆蓋問(wèn)題；柵欄覆蓋研究運(yùn)動(dòng)物體穿越網(wǎng)絡(luò)部署區(qū)域被發(fā)現(xiàn)的概率問(wèn)題。相對(duì)而言，對(duì)區(qū)域覆蓋的研究較多。如果目標(biāo)區(qū)域中的任何一點(diǎn)都被k個(gè)傳感器節(jié)點(diǎn)監(jiān)測(cè)，就稱網(wǎng)絡(luò)是k-覆蓋的，或者稱網(wǎng)絡(luò)的覆蓋度為k。一般要求目標(biāo)區(qū)域的每一個(gè)點(diǎn)至少被一個(gè)節(jié)點(diǎn)監(jiān)測(cè)，即1-覆蓋。
3）吞吐量化簡(jiǎn)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)應(yīng)該能夠支持與原始網(wǎng)絡(luò)相似的通信量，尤其是在有大量突發(fā)事件時(shí)。設(shè)目標(biāo)區(qū)域是一個(gè)凸區(qū)域，每個(gè)節(jié)點(diǎn)的吞吐率為λ bps。在理想情況下有下面的關(guān)系式[3]：
λ≤(16AW/πΔ2L)(1/nr)bps
其中：A是目標(biāo)區(qū)域的面積；W是節(jié)點(diǎn)的最高傳輸速率；π是圓周率；Δ是大于0的常數(shù)；L是源節(jié)點(diǎn)到目的節(jié)點(diǎn)的平均距離；n是節(jié)點(diǎn)數(shù)；r是理想球狀無(wú)線電發(fā)射模型的發(fā)射半徑。由此可以看出，減小發(fā)射半徑或減小工作網(wǎng)絡(luò)的規(guī)模，在節(jié)省能量的同時(shí)可以在一定程度上提高網(wǎng)絡(luò)的吞吐能力。
4)魯棒性當(dāng)在原始圖G中的鄰近關(guān)系發(fā)生變化時(shí)(如節(jié)點(diǎn)運(yùn)動(dòng)、失效或無(wú)線信道特性發(fā)生變化)，一些節(jié)點(diǎn)的拓?fù)湫畔⒖赡軙?huì)發(fā)生變化。顯然魯棒的拓?fù)浣Y(jié)構(gòu)只需進(jìn)行少量的調(diào)整就可以避免對(duì)本地節(jié)點(diǎn)重新組織而造成整個(gè)網(wǎng)絡(luò)的波動(dòng)。
5）算法總開(kāi)銷(xiāo)對(duì)于資源有限的節(jié)點(diǎn)來(lái)說(shuō)，算法本身的開(kāi)銷(xiāo)應(yīng)該小一些，如附加信息少、計(jì)算量小；另外分布式實(shí)現(xiàn)也是一個(gè)必要條件。
在當(dāng)前的無(wú)線傳感器網(wǎng)絡(luò)中，連通性、覆蓋性和擴(kuò)展因子可能是除了必不可少的分布式性質(zhì)和低開(kāi)銷(xiāo)量之外的拓?fù)淇刂扑惴ㄗ钪匾奶匦浴３酥猓負(fù)淇刂七€要考慮網(wǎng)絡(luò)的生存周期、網(wǎng)絡(luò)中的干擾和競(jìng)爭(zhēng)、延遲、拓?fù)湫再|(zhì)、負(fù)載均衡等其他方面，拓?fù)淇刂频母鞣N設(shè)計(jì)目標(biāo)之間有著復(fù)雜的關(guān)系，這些關(guān)系也是拓?fù)淇刂蒲芯康闹匾獌?nèi)容。
2平面網(wǎng)絡(luò)中的拓?fù)淇刂啤β士刂篇?/p>
在平面網(wǎng)絡(luò)中，所有的節(jié)點(diǎn)都是同構(gòu)的，具有同樣的硬件、同樣的能力，完成同樣的任務(wù)。在平面網(wǎng)絡(luò)中拓?fù)淇刂谱罨镜姆椒ㄊ强刂婆c一個(gè)節(jié)點(diǎn)通信的鄰節(jié)點(diǎn)集。而這個(gè)問(wèn)題與控制節(jié)點(diǎn)的發(fā)射功率有著密切的關(guān)系，所以一般稱為功率控制。
目前，對(duì)平面網(wǎng)絡(luò)的拓?fù)淇刂蒲芯糠椒ㄖ饕譃閮深?lèi)：a)概率分析的方法，在節(jié)點(diǎn)按照某種概率密度分布的情況下，計(jì)算使拓?fù)錆M足某些性質(zhì)(一般是連通性、覆蓋率)所需要的最小發(fā)射功率和最小鄰節(jié)點(diǎn)個(gè)數(shù)；b)計(jì)算幾何方法，以某些幾何結(jié)構(gòu)為基礎(chǔ)構(gòu)建網(wǎng)絡(luò)拓?fù)洌詽M足某些性質(zhì)。
2.1概率分析方法
研究人員針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)提出了幾何隨機(jī)圖理論。假設(shè)網(wǎng)絡(luò)采用單位圓盤(pán)圖模型(unit disk graph，UDG)以及在給定面積為A的區(qū)域內(nèi)節(jié)點(diǎn)是均勻分布的，這個(gè)假設(shè)模型正好對(duì)應(yīng)于幾何隨機(jī)圖理論。
文獻(xiàn)[4]采用了一種基于幾何隨機(jī)圖的類(lèi)似算法來(lái)確定圖是k-連通的概率表達(dá)式，如果節(jié)點(diǎn)的發(fā)射功率大到足以保證圖的最小度數(shù)至少為k(概率很大)，那么有大量節(jié)點(diǎn)的圖就是k-連通的。Bettstetter利用這個(gè)結(jié)論推導(dǎo)出了一個(gè)圖中最小節(jié)點(diǎn)度的概率公式:
P(G是連通的) ≈1-∑k-1l=0(ρπr2)l/l!·e-ρπr2
(1)
其中：r為節(jié)點(diǎn)的發(fā)射半徑；ρ為節(jié)點(diǎn)的密度(假設(shè)節(jié)點(diǎn)在給定區(qū)域內(nèi)均勻分布)。
Li等人[5]也研究過(guò)k-連通問(wèn)題，提出了當(dāng)發(fā)射半徑r在k＞0時(shí)滿足nπr2≥ln n+(2k-1) ln ln n-2 ln k+2α且n足夠大時(shí)，節(jié)點(diǎn)數(shù)為n的網(wǎng)絡(luò)(k+1)連通的概率至少是ee-α。
如果網(wǎng)絡(luò)中的節(jié)點(diǎn)并不是均勻分布的，尤其是稀疏網(wǎng)絡(luò)，那么幾何隨機(jī)圖理論就無(wú)法應(yīng)用，但是研究人員對(duì)此也做了一些工作。Santi等人[6]假設(shè)n個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)數(shù)固定，也可能變化)在d維部署區(qū)域R＝[0，l]d內(nèi)隨機(jī)均勻部署，對(duì)于節(jié)點(diǎn)密度ρ=n/ld沒(méi)有限制，他們的目標(biāo)是使所有節(jié)點(diǎn)都具有最小半徑發(fā)射半徑r，使得到的圖是連通的。
對(duì)一維d=1的情況，可以證明，如果rn≥2l ln l，那么圖是連通的概率很高；如果rn≤l ln l，圖是非連通的概率很高。對(duì)于d=2，3的情況，給出了如下結(jié)論：
對(duì)于某常數(shù)k＞0，設(shè)rdl=kld ln l，r=r(l)＜＜l和n=n(l)＞＞1。如果k＞d×2d dd/2(或k=d×2ddd/2及r=r(l)＞＞1)，那么圖是連通的概率很高。
設(shè)r=r(l)＜＜l和n=n(l)＞＞1。如果f d∈O(ld)，那么圖是非連通的概率很高。
還有其他一些平面網(wǎng)絡(luò)的研究結(jié)果，Kubisch等人[7]描述了兩種將鄰節(jié)點(diǎn)數(shù)控制在一定數(shù)量?jī)?nèi)的分布式算法，并通過(guò)仿真實(shí)驗(yàn)評(píng)價(jià)了它們的性能。Liu等人[8]研究了關(guān)于節(jié)點(diǎn)有不同最大發(fā)射范圍的問(wèn)題，得到了非連接的信息，采用了一個(gè)分布式拓?fù)浣Y(jié)構(gòu)控制算法來(lái)最小化最大功率，保持了每個(gè)節(jié)點(diǎn)的可達(dá)性。Royer等人[9]研究了功率控制和移動(dòng)性的關(guān)系，功率控制與Ad hoc路由協(xié)議之間的相互作用，即Ad hoc按需距離矢量(AODV)的性能，證明了不存在最優(yōu)密度，但是密度會(huì)隨著節(jié)點(diǎn)的運(yùn)動(dòng)而增大。當(dāng)前大部分研究把功率控制看做與網(wǎng)絡(luò)中其他層是無(wú)關(guān)的。Cruz等人[10]研究了跨層問(wèn)題，提出了一個(gè)結(jié)合連接調(diào)度表和功率控制的算法。
2.2計(jì)算幾何方法
如果能夠獲得節(jié)點(diǎn)之間的距離或它們的相對(duì)位置的信息，那么可以有效地實(shí)現(xiàn)將網(wǎng)絡(luò)拓?fù)渥兊孟∈琛＠糜?jì)算幾何方法構(gòu)建鄰近圖的方法能夠?qū)崿F(xiàn)拓?fù)淇刂啤＝?jīng)常使用的幾何結(jié)構(gòu)有以下幾種：
a)最小生成樹(shù)(MST)。文獻(xiàn)[11]提出了一種基于本地信息的最小生成樹(shù)的構(gòu)造法，其思想是每個(gè)節(jié)點(diǎn)會(huì)收集它的鄰節(jié)點(diǎn)，然后構(gòu)造(如使用prim算法)這些節(jié)點(diǎn)的最小生成樹(shù)，將能量代價(jià)作為連接權(quán)重(代價(jià)相同的連接由加入的節(jié)點(diǎn)表示符作為間斷符來(lái)區(qū)分)。下一步的關(guān)鍵就是在化簡(jiǎn)后的拓?fù)渲斜Ａ暨@些對(duì)應(yīng)于最小生成樹(shù)中直接鄰節(jié)點(diǎn)的邊。這種構(gòu)造法保持了原圖的連通性，而且每個(gè)節(jié)點(diǎn)的最大度數(shù)是6。它能限制雙向連接，也比較容易加入功率控制。而且，平均節(jié)點(diǎn)度數(shù)比較小，接近理論界限。
b)Gabriel圖(Gabriel graph，GG)。在傳輸功率正比傳輸距離的平方時(shí)，GG是最節(jié)能的拓?fù)洹ST是GG的子圖，GG也滿足連通性。 在文獻(xiàn)[12]中介紹了GG的分布式構(gòu)造法。一個(gè)節(jié)點(diǎn)必須要對(duì)于它的所有鄰節(jié)點(diǎn)都測(cè)試邊的圈定義是否還成立，如果所有的節(jié)點(diǎn)都與它們的鄰節(jié)點(diǎn)的位置相交換，那么這是很容易做到的。
c)相關(guān)鄰近圖（relative neighbor graph，RNG），很容易用本地算法實(shí)現(xiàn)。如果原始圖G是連通的，那么它也是連通的。其稀疏程度在MST和GG之間，連通性也在MST和GG之間，優(yōu)于MST，沖突干擾優(yōu)于GG，是兩者的折中。RNG易于用分布式算法構(gòu)造。
Li等人[13]提出的DRNG和DLMST是兩個(gè)具有代表性的基于鄰近圖理論的算法。基于鄰近圖的功率控制算法的基本思想是：設(shè)所有節(jié)點(diǎn)都是用最大發(fā)射功率發(fā)射時(shí)形成的拓?fù)鋱DG，按照一定的鄰居判別條件求出該圖的鄰近圖G′，每個(gè)節(jié)點(diǎn)以自己所鄰近的最遠(yuǎn)節(jié)點(diǎn)來(lái)確定發(fā)射功率。DRNG是基于有向RNG的，DLMST是基于有向局部MST的。DRNG和DLMST能夠保證網(wǎng)絡(luò)的連通性，在平均功率和節(jié)點(diǎn)度等方面具有良好的性能。
平面網(wǎng)絡(luò)的功率控制算法除了上面兩類(lèi)基本類(lèi)型之外，研究人員也提出了一些其他算法，如分布式公共功率協(xié)議COMPOW[14]，K-NEIGH協(xié)議[15]等。
分布式公共功率協(xié)議COMPOW。簡(jiǎn)單地將功率控制與路由協(xié)議相結(jié)合的解決方案。其基本思想是：所有的傳感器節(jié)點(diǎn)使用同樣的發(fā)射功率，在保證網(wǎng)絡(luò)連通的前提下，將功率最小化。COMPOW在各個(gè)功率層上建立路由表，在功率Pi層上，通過(guò)使用功率Pi交換HELLO消息建立路由表RTPi，所有可達(dá)節(jié)點(diǎn)都是路由表中的表項(xiàng)。COMPOW選擇最小的發(fā)射功率Pcom，使得RTPcow和RTPmax具有相同的表項(xiàng)。其中Pmax是最大發(fā)射功率。于是整個(gè)網(wǎng)絡(luò)都使用公共的發(fā)射功率Pcom。在節(jié)點(diǎn)分布均勻的情況下，COMPOW具有較好的性能，但是一個(gè)相對(duì)孤立的節(jié)點(diǎn)會(huì)導(dǎo)致所有的節(jié)點(diǎn)使用很大的發(fā)射功率。另外這個(gè)理論雖然實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，但是它需要保留所有潛在節(jié)點(diǎn)的路由表，這一點(diǎn)使得它基本上不適合無(wú)線傳感器網(wǎng)絡(luò)。
K-NEIGH協(xié)議的思想是使每個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)數(shù)保持k個(gè)或接近于k個(gè)。這個(gè)協(xié)議是分布式的，基于節(jié)點(diǎn)間的距離是估計(jì)的，而且需要總量為2｜V｜的信息交換量。這種方法是節(jié)點(diǎn)用大發(fā)射功率發(fā)布它們的信標(biāo)，收集它們觀察到的鄰節(jié)點(diǎn)的信息，按距離對(duì)鄰節(jié)點(diǎn)進(jìn)行分類(lèi)，并計(jì)算能夠互相到達(dá)的k個(gè)最近的鄰節(jié)點(diǎn)，這樣每個(gè)節(jié)點(diǎn)用最小的發(fā)射功率就能到達(dá)剛才計(jì)算的所有鄰節(jié)點(diǎn)。在這個(gè)協(xié)議的設(shè)計(jì)中，需要注意的是要等待足夠長(zhǎng)的時(shí)間隨機(jī)地喚醒節(jié)點(diǎn)，以及適當(dāng)解決潛在的非對(duì)稱鏈路的問(wèn)題。
3層次型網(wǎng)絡(luò)中的拓?fù)淇刂平Y(jié)構(gòu)
研究無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的另一種方法是在網(wǎng)絡(luò)節(jié)點(diǎn)中形成一種層次關(guān)系，構(gòu)成一個(gè)層次型的網(wǎng)絡(luò)。目前主要有兩種研究手段，即采用支配集的層次型網(wǎng)絡(luò)和采用分簇結(jié)構(gòu)的層次型網(wǎng)絡(luò)。
3.1采用支配集的層次型網(wǎng)絡(luò)
在網(wǎng)絡(luò)中選出一些虛擬骨干節(jié)點(diǎn)組成虛擬骨干網(wǎng)，這些節(jié)點(diǎn)又叫做支配集，即如果V中所有節(jié)點(diǎn)或在D中，或是某個(gè)節(jié)點(diǎn)d∈D的單跳鄰節(jié)點(diǎn)(v∈V:v∈D∨d∈D:(v，d)∈E)，這里D就是支配集。而這個(gè)支配集在某種程度上應(yīng)該盡量小，這也是最小支配集問(wèn)題(minimum dominating set，MDS)。
文獻(xiàn)[16]介紹了兩種集中式的例子。a)生成樹(shù)結(jié)構(gòu)。主要思想是像生成樹(shù)型結(jié)構(gòu)一樣構(gòu)造支配集，迭代地給樹(shù)加入舊節(jié)點(diǎn)和邊，直到所有的舊節(jié)點(diǎn)都被覆蓋為止。這個(gè)算法用節(jié)點(diǎn)的顏色來(lái)表示：白色節(jié)點(diǎn)表示沒(méi)有被處理，黑色節(jié)點(diǎn)屬于支配集，灰色節(jié)點(diǎn)表示受控集。b)先構(gòu)造一個(gè)不一定連通的支配集，然后在下一個(gè)階段，把集合內(nèi)的所有節(jié)點(diǎn)連接在一起。把非連通的支配集連通起來(lái)也叫做尋找斯坦納樹(shù)(Steiner tree)問(wèn)題。
生成樹(shù)的分布式算法可以由文獻(xiàn)[17]介紹的分布式算法來(lái)實(shí)現(xiàn)。從本質(zhì)上來(lái)說(shuō)，就是所有灰色節(jié)點(diǎn)發(fā)現(xiàn)它們的兩跳鄰節(jié)點(diǎn)，并確定每個(gè)節(jié)點(diǎn)能夠得到的最大收益，然后分布式地選擇最大收益，就可以確定下一個(gè)黑色節(jié)點(diǎn)了。
TopDisc(topology discovery)算法[18]來(lái)源于圖論的思想，是基于最小支配集問(wèn)題的經(jīng)典算法。它利用顏色區(qū)分節(jié)點(diǎn)狀態(tài)，解決骨干網(wǎng)拓?fù)浣Y(jié)構(gòu)的形成問(wèn)題。在TopDisc 算法中，由網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)啟動(dòng)發(fā)送用于發(fā)現(xiàn)鄰節(jié)點(diǎn)的查詢消息，查詢消息攜帶發(fā)送節(jié)點(diǎn)的狀態(tài)信息。隨著查詢消息在網(wǎng)絡(luò)中傳播，TopDisc 算法依次為每個(gè)節(jié)點(diǎn)標(biāo)記顏色。最后，按照節(jié)點(diǎn)顏色區(qū)分出骨干網(wǎng)節(jié)點(diǎn)，并通過(guò)反向?qū)ふ也樵兿⒌膫鞑ヂ窂皆诠歉删W(wǎng)節(jié)點(diǎn)之間建立通信鏈路。每個(gè)骨干網(wǎng)節(jié)點(diǎn)管理與自己相鄰的普通節(jié)點(diǎn)。
TopDisc 算法中提出了兩種具體的節(jié)點(diǎn)狀態(tài)標(biāo)記辦法，分別稱為三色算法和四色算法。這兩種算法的區(qū)別在于尋找骨干網(wǎng)節(jié)點(diǎn)的標(biāo)準(zhǔn)不一樣，所以最后形成的拓?fù)浣Y(jié)構(gòu)也有所不同。
3.2采用簇結(jié)構(gòu)的層次型結(jié)構(gòu)
前面介紹了通過(guò)把一些節(jié)點(diǎn)作為骨干節(jié)點(diǎn)形成支配集，把層次結(jié)構(gòu)引入了網(wǎng)絡(luò)。另一種形成層次結(jié)構(gòu)的想法是把一些節(jié)點(diǎn)標(biāo)記為具有特殊的功能，如控制其鄰節(jié)點(diǎn)等，這樣就形成了簇，這個(gè)具有特殊功能的節(jié)點(diǎn)就叫做簇首。這種分簇方法的優(yōu)點(diǎn)與骨干節(jié)點(diǎn)類(lèi)似，但是更著重于本地資源的優(yōu)化使用，能夠屏蔽網(wǎng)絡(luò)高層的動(dòng)態(tài)特性，使高層協(xié)議更具有可擴(kuò)展性，另外簇首還能夠進(jìn)行本地?cái)?shù)據(jù)融合、壓縮任務(wù)。
LEACH(low energy adaptive clustering hierarchy)[19]算法是一種自適應(yīng)分簇算法，它的執(zhí)行過(guò)程是周期性的，每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。在簇的建立階段，相鄰節(jié)點(diǎn)動(dòng)態(tài)地形成簇，隨機(jī)產(chǎn)生簇首；在數(shù)據(jù)通信階段，簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)發(fā)送給簇首，簇首進(jìn)行數(shù)據(jù)融合并把結(jié)果發(fā)送給匯聚節(jié)點(diǎn)。由于簇首需要完成數(shù)據(jù)融合、與匯聚節(jié)點(diǎn)通信等工作，能量消耗大，LEACH算法能夠保證各節(jié)點(diǎn)等概率地?fù)?dān)任簇首，使得網(wǎng)絡(luò)中的節(jié)點(diǎn)相對(duì)均衡地消耗能量。
GAF算法[20]是基于地理位置的拓?fù)渌惴ǎ撬鼪](méi)有考慮節(jié)點(diǎn)的剩余能量，而是隨機(jī)地選擇節(jié)點(diǎn)作為簇首。該算法中的簇首承擔(dān)更多的數(shù)據(jù)處理和通信任務(wù)，消耗的能量相對(duì)較大，因此，簇首應(yīng)該選擇剩余能量較多的節(jié)點(diǎn)。P.Santi等人[21]提出了一種GAF改進(jìn)算法，他設(shè)計(jì)了兩種不同的簇首選擇機(jī)制，并詳細(xì)分析了簇首節(jié)點(diǎn)產(chǎn)生后的網(wǎng)絡(luò)運(yùn)行方式，同時(shí)驗(yàn)證了改進(jìn)的GAF算法對(duì)網(wǎng)絡(luò)生存時(shí)間的影響。與GAF算法相比，GAF改進(jìn)算法除了要求每個(gè)節(jié)點(diǎn)知道自己的ID以及屬于哪個(gè)單元格外，還要求同一單元格中的節(jié)點(diǎn)保持時(shí)間同步。GAF改進(jìn)算法有兩種簇首選擇機(jī)制，即完全型簇首選擇算法和隨機(jī)型簇首選擇算法。虛擬單元格建立起來(lái)后，每個(gè)節(jié)點(diǎn)都知道自己所屬的虛擬單元格。節(jié)點(diǎn)根據(jù)已知本單元格相關(guān)信息的多少?zèng)Q定采取哪種簇首節(jié)點(diǎn)選擇機(jī)制。
HEED[22]的基本思想是：根據(jù)對(duì)作為第一因素的剩余能量和作為第二因素的簇內(nèi)通信代價(jià)的綜合考慮，周期性地通過(guò)迭代的辦法實(shí)現(xiàn)分簇。HEED用最小平均可達(dá)功率(AMRP)作為當(dāng)某個(gè)節(jié)點(diǎn)被選為簇首時(shí)的簇內(nèi)通信代價(jià)的度量。
HEED不依賴于網(wǎng)絡(luò)的規(guī)模，通過(guò)O(1)次迭代實(shí)現(xiàn)分簇。迭代每一步的時(shí)間要足夠長(zhǎng)，使得節(jié)點(diǎn)能夠收到來(lái)自鄰節(jié)點(diǎn)的消息。初始時(shí)，每個(gè)節(jié)點(diǎn)要確定在一跳范圍內(nèi)的鄰節(jié)點(diǎn)的集合，計(jì)算并廣播AMRP，計(jì)算自己成為臨時(shí)簇首的初始概率CHp。
HEED綜合考慮了生存時(shí)間、可擴(kuò)展性和負(fù)載均衡，對(duì)節(jié)點(diǎn)的分布和能力也沒(méi)有特殊要求，雖然HEED的執(zhí)行并不依賴于同步，但是不同步卻會(huì)嚴(yán)重影響分簇的質(zhì)量。
4層次型拓?fù)浣Y(jié)構(gòu)與功率控制相結(jié)合
層次型方法(骨干網(wǎng)節(jié)點(diǎn)控制、成簇控制)和平面網(wǎng)絡(luò)中功率控制都是影響無(wú)線網(wǎng)絡(luò)拓?fù)涞挠行Х椒ā，F(xiàn)在的一個(gè)研究方向就是將這兩種機(jī)制結(jié)合在一起。
1)基于引導(dǎo)信號(hào)的功率控制[23]
這是一種早期的方法，簇首用這種方法來(lái)進(jìn)行功率控制，與在蜂窩網(wǎng)絡(luò)中進(jìn)行的功率控制相類(lèi)似。在建立初始的分簇結(jié)構(gòu)之后，簇首在引導(dǎo)信號(hào)和數(shù)據(jù)通信中使用功率控制。如果基于這些引導(dǎo)信號(hào)，所有節(jié)點(diǎn)都加入了同一個(gè)簇，那么就可以使用引導(dǎo)信號(hào)功率控制來(lái)控制簇的成員。數(shù)據(jù)通信功率控制用于保證遠(yuǎn)處節(jié)點(diǎn)的誤碼率足夠低以及對(duì)附近節(jié)點(diǎn)能高效地發(fā)送信息；它也能防止出現(xiàn)非常差的發(fā)射條件。功率控制的主要優(yōu)點(diǎn)是它在簇首中是集中式的，這簡(jiǎn)化了完全分布式的功率控制問(wèn)題。
2)Ad hoc網(wǎng)絡(luò)設(shè)計(jì)算法
Ad hoc網(wǎng)絡(luò)設(shè)計(jì)算法(Ad hoc network design algorithm，ANDA)[24]允許簇首通過(guò)功率控制來(lái)控制簇的大小，并且導(dǎo)出了一些具體的規(guī)則以盡可能延長(zhǎng)網(wǎng)絡(luò)的生存期。假設(shè)網(wǎng)絡(luò)的生存期主要由簇首決定，因?yàn)榇厥棕?fù)責(zé)收集、轉(zhuǎn)發(fā)感知信息，完成最主要的任務(wù)，能量消耗應(yīng)該在簇首間均衡。
這個(gè)方法的基本假設(shè)是:a)普通節(jié)點(diǎn)和(預(yù)選出的)簇首的位置是已知的；b)通信量在普通節(jié)點(diǎn)間均勻分布；c)簇首的生存期與它的初始能量成正比，與crα+dn成反比。其中：r是簇首覆蓋區(qū)域的半徑；n是簇內(nèi)成員的個(gè)數(shù)；α是路徑損耗系數(shù)；c、d是常數(shù)。算法的最佳目標(biāo)是使所有簇首的生存期最長(zhǎng)，或者相應(yīng)地使簇首中的最小生存期最長(zhǎng)。
這種求最大值的問(wèn)題是一個(gè)優(yōu)化問(wèn)題，用決策變量來(lái)描述簇j中普通節(jié)點(diǎn)i的成員身份。其中也隱含著所需的發(fā)射半徑。對(duì)于靜態(tài)網(wǎng)絡(luò)來(lái)說(shuō)，用一個(gè)簡(jiǎn)單的貪婪算法就能求得最優(yōu)解：將節(jié)點(diǎn)i分配給有最長(zhǎng)生存期的簇首，對(duì)所有節(jié)點(diǎn)重復(fù)這一操作。對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)來(lái)說(shuō)，需要一個(gè)額外的重新配置過(guò)程，而且無(wú)法保證求得的是最優(yōu)解，但其實(shí)際性能還不錯(cuò)。
3)CLUSTERPOW
前面討論了在節(jié)點(diǎn)分布均勻的情況下，COMPOW算法具有較好的性能，但是，一個(gè)相對(duì)孤立的節(jié)點(diǎn)會(huì)導(dǎo)致所有的節(jié)點(diǎn)使用很大的發(fā)射功率，所以在節(jié)點(diǎn)分布不均勻的情況下，它的缺點(diǎn)是明顯的。針對(duì)這種缺點(diǎn)，改進(jìn)了COMPOW協(xié)議，提出了CLUSTERPOW協(xié)議[25]。它的基本思想是簡(jiǎn)單地假設(shè)一組離散的發(fā)射功率值，如1、10、100 mW。在每個(gè)功率值處，簇都是獨(dú)立形成的，而且對(duì)于每個(gè)功率值都有單獨(dú)的路由表。如果用最小功率就能保證到達(dá)目的節(jié)點(diǎn)，那么就發(fā)送數(shù)據(jù)，一旦數(shù)據(jù)進(jìn)入了包含目的節(jié)點(diǎn)的最小功率簇后，功率值就會(huì)被降低。在CLUSTERPOW中，分簇是隱含的，且無(wú)須任何簇首節(jié)點(diǎn)，分簇通過(guò)給定功率層的可達(dá)性來(lái)實(shí)現(xiàn)，分簇的層次由功率的層次數(shù)來(lái)實(shí)現(xiàn)，分簇是動(dòng)態(tài)的、分布的。
對(duì)較大的初始發(fā)射功率進(jìn)行替換是很有用的。為了實(shí)現(xiàn)這個(gè)目標(biāo)，在相關(guān)文獻(xiàn)中也描述了隧道式CLUSTERPOW協(xié)議。在這種情況下，為了避免無(wú)限地路由循環(huán)，必須將用于以最小功率進(jìn)行路由的中間節(jié)點(diǎn)的地址也裝入數(shù)據(jù)分組中。
5其他一些啟發(fā)式算法
還有一些其他的拓?fù)淇刂扑惴ǎ⒉皇菄?yán)格地符合利用骨干節(jié)點(diǎn)/支配集計(jì)算或分簇原理的，它們都是通過(guò)打開(kāi)或關(guān)閉某些節(jié)點(diǎn)來(lái)影響圖的拓?fù)浣Y(jié)構(gòu)。顯然，源節(jié)點(diǎn)和數(shù)據(jù)匯聚節(jié)點(diǎn)總是活動(dòng)的。
1)基于地理位置的拓?fù)渌惴?GAF)
Xu等人在文獻(xiàn)[20]中提出了基于地理位置的拓?fù)渌惴ǎ乃枷胧菍^(qū)域分成非常小的矩形，使每個(gè)矩形中的節(jié)點(diǎn)都能與相鄰矩形中的節(jié)點(diǎn)進(jìn)行通信。如果某些節(jié)點(diǎn)滿足某些條件，那么這些節(jié)點(diǎn)從網(wǎng)絡(luò)的高層(如路由層)來(lái)看可以看做是等價(jià)的。當(dāng)一個(gè)節(jié)點(diǎn)休眠時(shí)，可以激活它的等價(jià)節(jié)點(diǎn)來(lái)替代。
假設(shè)節(jié)點(diǎn)都知道它們自己的位置，所以這些節(jié)點(diǎn)能很容易地構(gòu)成這樣的等效矩形，并在它們自己的矩形中確定節(jié)點(diǎn)。這些節(jié)點(diǎn)之間互相合作確定休眠模式，按順序參加路由協(xié)議。Xu等人證明了使用這種方案，Ad hoc路由協(xié)議的能量效率能被提高40％～60％。
2)STEM算法
在GAF(或其他有等價(jià)節(jié)點(diǎn)概念的方法)的基礎(chǔ)上，可以加入稀疏拓?fù)浜湍芰抗芾?sparse topology and energy management)協(xié)議[26]。
STEM是節(jié)點(diǎn)喚醒算法，在STEM算法中，節(jié)點(diǎn)需要采用一種簡(jiǎn)單而迅速的節(jié)點(diǎn)喚醒方式，保證網(wǎng)絡(luò)通信的暢通和較小的延遲。該算法又包括兩種不同的機(jī)制，即STEM-B和STEM-T。它使節(jié)點(diǎn)在整個(gè)生命周期中大多數(shù)時(shí)間內(nèi)處于睡眠狀態(tài)。節(jié)點(diǎn)的睡眠周期、部署密度以及網(wǎng)絡(luò)的傳輸延遲之間有著密切的關(guān)系。GAF關(guān)閉節(jié)點(diǎn)，但是卻保持網(wǎng)絡(luò)的轉(zhuǎn)發(fā)容量；虛擬喚醒信道的STEM機(jī)制提高了能量效率，卻也增大了路徑建立的延遲。Schurgers等人[26]建議將這兩種方法結(jié)合起來(lái)，即把STEM算法應(yīng)用于GAF算法中等價(jià)的節(jié)點(diǎn)集合之中。
3)可變的自適應(yīng)拓?fù)渌惴?ASCENT)
加州大學(xué)洛杉磯分校的Cerpa等人[27]提出了一種著重于保證數(shù)據(jù)通路暢通的ASCENT算法。保留一定數(shù)量的節(jié)點(diǎn)作為路由節(jié)點(diǎn)，其余節(jié)點(diǎn)轉(zhuǎn)入休眠狀態(tài)，但是節(jié)點(diǎn)不僅根據(jù)附近節(jié)點(diǎn)的通信量來(lái)確定是否成為活動(dòng)節(jié)點(diǎn)，還要考慮丟包率指標(biāo)。如果某個(gè)節(jié)點(diǎn)發(fā)現(xiàn)丟包嚴(yán)重，就向鄰節(jié)點(diǎn)發(fā)出求救信息；收到求救信息的節(jié)點(diǎn)主動(dòng)成為工作節(jié)點(diǎn)，幫助鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包。但是，ASCENT并不能保證網(wǎng)絡(luò)的連通性，因?yàn)樗皇峭ㄟ^(guò)丟包率來(lái)判斷連通性的。事實(shí)上，當(dāng)網(wǎng)絡(luò)不連通時(shí)，它是無(wú)法檢測(cè)和修復(fù)的。ASCENT也不能保證能量的均勻消耗。
節(jié)點(diǎn)可以關(guān)閉自己，但是必須周期性地進(jìn)入被動(dòng)狀態(tài)來(lái)監(jiān)聽(tīng)?zhēng)椭?qǐng)求。對(duì)網(wǎng)絡(luò)性能的監(jiān)測(cè)依賴于拓?fù)淇刂疲@是ASCENT算法區(qū)別于其他算法的地方，但是，它有大量需要優(yōu)化的參數(shù)。
4)在傳感器覆蓋率的基礎(chǔ)上關(guān)閉節(jié)點(diǎn)
與傳統(tǒng)的Ad hoc網(wǎng)絡(luò)不同的是，對(duì)WSN來(lái)說(shuō)，只保證網(wǎng)絡(luò)的連通性是不夠的。WSN的主要任務(wù)是感知和測(cè)量它周?chē)沫h(huán)境。為了完成這項(xiàng)任務(wù)，無(wú)論是否需要連通性(可能是弱連通的)，觀測(cè)區(qū)域都必須被足夠多的節(jié)點(diǎn)覆蓋。通常，WSN的感測(cè)覆蓋率問(wèn)題是一個(gè)很難解決的問(wèn)題。
Tian等人[28]指出要關(guān)閉節(jié)點(diǎn)，就必須保證節(jié)點(diǎn)的感測(cè)覆蓋區(qū)域會(huì)由其他節(jié)點(diǎn)覆蓋。只有這樣的節(jié)點(diǎn)才有資格休眠一段時(shí)間。
假設(shè)節(jié)點(diǎn)知道它們的位置和它們的感測(cè)區(qū)域，在與它們的鄰節(jié)點(diǎn)交換信息后(如在循環(huán)的開(kāi)始)，節(jié)點(diǎn)確定它自己的感測(cè)區(qū)域是否被它的鄰節(jié)點(diǎn)所覆蓋，這只是一個(gè)簡(jiǎn)單的地理問(wèn)題。如果是，節(jié)點(diǎn)就聲明它可以休眠，并通知它的鄰節(jié)點(diǎn)，然后進(jìn)入休眠狀態(tài)。
如果所有可以休眠的節(jié)點(diǎn)同時(shí)進(jìn)入休眠狀態(tài)并立即關(guān)閉自己，就有出現(xiàn)盲點(diǎn)的危險(xiǎn)。如果兩個(gè)鄰節(jié)點(diǎn)均可以休眠，根據(jù)假設(shè)，它們認(rèn)為另一個(gè)節(jié)點(diǎn)會(huì)保持活動(dòng)(在另一邊剩余的未覆蓋區(qū)域會(huì)由其他更遠(yuǎn)的節(jié)點(diǎn)覆蓋)，就會(huì)發(fā)生這種情況。為了避免這種情況，休眠資格的通告是用通用的隨機(jī)補(bǔ)償算法進(jìn)行隨機(jī)延遲的。當(dāng)節(jié)點(diǎn)接收到這樣的信息時(shí)，它從它的鄰節(jié)點(diǎn)列表中將這個(gè)很快要進(jìn)入休眠狀態(tài)的節(jié)點(diǎn)刪除，并重新評(píng)估它自己的休眠資格。
這個(gè)算法基于節(jié)點(diǎn)是冗余部署這一事實(shí)的；否則不可能有節(jié)點(diǎn)可以休眠。這是一個(gè)簡(jiǎn)單而有效的方法，并且考慮了WSN的實(shí)際特性。
6存在的問(wèn)題及進(jìn)一步需要研究的內(nèi)容
上面總結(jié)了當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯恐凶罹叽硇缘墓ぷ鳎瑫r(shí)也指出了存在的問(wèn)題。
1)拓?fù)淇刂贫x問(wèn)題
現(xiàn)在對(duì)拓?fù)淇刂七€沒(méi)有一個(gè)清晰的定義，在文獻(xiàn)[29]中，P.Santi提出了一個(gè)非正式的定義：拓?fù)淇刂剖菫榱松梢粋€(gè)具有某種屬性(如連通性)的網(wǎng)絡(luò)，協(xié)調(diào)網(wǎng)絡(luò)中的節(jié)點(diǎn)決定它們傳輸范圍的一種技術(shù)，同時(shí)能夠減少節(jié)點(diǎn)的能量消耗和(或)增加網(wǎng)絡(luò)的容量。作者區(qū)分了一般的節(jié)點(diǎn)節(jié)能技術(shù)、節(jié)點(diǎn)功率控制技術(shù)和拓?fù)淇刂萍夹g(shù)的區(qū)別，同時(shí)又認(rèn)為成簇技術(shù)是控制網(wǎng)絡(luò)拓?fù)涞囊环N手段，因?yàn)槌纱剡^(guò)程中節(jié)點(diǎn)的發(fā)射功率是固定的，所以成簇技術(shù)并不是一種拓?fù)淇刂萍夹g(shù)。現(xiàn)在大多數(shù)人認(rèn)為拓?fù)淇刂萍夹g(shù)是在保證一定的網(wǎng)絡(luò)屬性(如連通性、覆蓋性等)的前提下，以延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間為目標(biāo)，采用各種技術(shù)使網(wǎng)絡(luò)形成一個(gè)優(yōu)化的網(wǎng)絡(luò)拓?fù)洌β士刂坪蛯哟涡途W(wǎng)絡(luò)控制都是手段。但是如何衡量是優(yōu)化的網(wǎng)絡(luò)呢？度量網(wǎng)絡(luò)的性能指標(biāo)是什么？目前平面網(wǎng)絡(luò)的功率控制以及層次型網(wǎng)絡(luò)控制的研究一般都是獨(dú)立進(jìn)行的，不同的應(yīng)用可能有不同的優(yōu)化目標(biāo)，性能指標(biāo)也不同，不太可能給出一個(gè)通用的定義。
2)拓?fù)淇刂圃趨f(xié)議棧中的位置
拓?fù)淇刂婆c協(xié)議棧的其他層關(guān)系密切，與物理層、鏈路層、網(wǎng)絡(luò)層和傳輸層交互作用。由于無(wú)線傳感器網(wǎng)絡(luò)中的協(xié)議棧中的各層之間的界限也已經(jīng)模糊，那么拓?fù)淇刂频降孜挥谀囊粚樱總鹘y(tǒng)認(rèn)為[29]拓?fù)淇刂莆挥贛AC層之上、路由層之下，它與路由層、MAC層之間的關(guān)系最為密切；但是也有人認(rèn)為拓?fù)淇刂品稚⒃诟鲗覽30]，所有這些都給協(xié)議棧設(shè)計(jì)帶來(lái)了困難。因此拓?fù)淇刂婆cMAC、路由、數(shù)據(jù)融合、數(shù)據(jù)存儲(chǔ)以及數(shù)據(jù)傳輸?shù)绕渌矫娼Y(jié)合的研究極大拓寬了拓?fù)淇刂频难芯款I(lǐng)域。
3)缺乏對(duì)拓?fù)淇刂扑惴ǖ挠行Ф攘开?/p>
拓?fù)淇刂埔岣呔W(wǎng)絡(luò)的各種性能，包括覆蓋質(zhì)量、能量消耗、連通質(zhì)量、干擾、延時(shí)、魯棒性等。但是目前還沒(méi)有對(duì)這些性能的有效度量的方法。一個(gè)實(shí)用的拓?fù)淇刂萍夹g(shù)其實(shí)應(yīng)該綜合考慮這些性能指標(biāo)，但到目前為止還沒(méi)有這樣的研究。有人提出了網(wǎng)絡(luò)生存周期，但是網(wǎng)絡(luò)生存周期沒(méi)有一個(gè)統(tǒng)一的定義，實(shí)際上網(wǎng)絡(luò)生存周期是一個(gè)綜合的抽象的性能指標(biāo)。如何有效地度量網(wǎng)絡(luò)的性能，也就是如何有效度量控制算法的性能，這些也是拓?fù)淇刂埔芯康膬?nèi)容。
由此看來(lái)，無(wú)線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂七€有很多問(wèn)題需要研究，這些問(wèn)題構(gòu)成了拓?fù)淇刂蒲芯康膬?nèi)容，這些研究?jī)?nèi)容之間又是相互制約、密不可分的。
7結(jié)束語(yǔ)
本文簡(jiǎn)要地描述了無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂频难芯楷F(xiàn)狀以及其中存在的一些問(wèn)題。現(xiàn)在拓?fù)淇刂蒲芯康陌l(fā)展趨勢(shì)是以實(shí)際應(yīng)用為背景，多種機(jī)制結(jié)合使用，強(qiáng)調(diào)網(wǎng)絡(luò)拓?fù)淇刂频淖赃m應(yīng)性和魯棒性，在保證網(wǎng)絡(luò)連通性和覆蓋度的前提下，提高網(wǎng)絡(luò)的通信效率，最大限度地節(jié)省能量來(lái)延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間。但是目前的研究還普遍存在著模型過(guò)于理想化，對(duì)網(wǎng)絡(luò)性能的綜合考慮比較少，研究結(jié)果缺乏足夠的說(shuō)服力，沒(méi)有考慮實(shí)際應(yīng)用中的困難。拓?fù)淇刂七€有許多問(wèn)題有待進(jìn)一步研究，特別是要根據(jù)實(shí)際應(yīng)用情況探索更加實(shí)用的拓?fù)淇刂萍夹g(shù)。以實(shí)際應(yīng)用為背景、多種機(jī)制相結(jié)合、綜合考慮網(wǎng)絡(luò)各種性能將是拓?fù)淇刂蒲芯康陌l(fā)展趨勢(shì)。
參考文獻(xiàn)：
[1]AKYILDIZ I F SU W SANKARASUBRAMANIAS Y，et al.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8):102-114.
[2]THAI M T WANG F DU D Z. Coverage problems in wireless sensor networks:designs and analysis[J].International Journal of Sensor Networks 2008，3(3):191-200.
[3]GUPTA P KUMAR P R. The capacity of wireless networks[J].IEEE Trans on Information Theory，2000，46(2):388-404.
[4]BETTSTETTER C. On the minimum node degree and connectivity of a wireless multihop network[M]. Los Alamitos: IEEE Computer Society Press，2002:80-91.
[5]LI Xiang-yang WAN Peng-jun WANG Yu et al. Fault tolerant deployment and topology control in wireless networks[C]//Proc of the 4th ACM Symposium on Mobile Ad hoc Networking and Computing. New York:ACM Press，2003:117-128.
[6]SANTI P BLOUGH D M. The critical transmitting range for connectivity in sparse wireless Ad hoc networks[J].IEEE Trans on Mobile Computing 2003，2(1):25-39.
[7]KUBISCH M KARL H WOLISZ A，et al. Distributed algorithms for transmission power control in wireless sensor networks[C]//Proc of IEEE Wireless Communications and Networking(WCNC).New York: IEEE Press 2003:558-563.
[8]LIU Ji-lei LI Bao-chun. Distributed topology control in wireless sensor networks with asymmetric links[C]//Proc of IEEE Globecom Wireless Communications Symposium. San Francisco:[s.n.] 2003.
[9]ROYER E M，MELLIAR-SMITH P M，MOSER L E.An analysis of the optimum node density for Ad hoc mobile networks[C]//Proc of IEEE International Conference on Communications.Helsinki:[s.n.] 2001:857-861.
[10]CRUZ R L SANTHANAM A V. Optimal routing link scheduling and power control in multi-hop wireless networks[C]//Proc of the 22nd Annual Joint Conference on IEEE Computer and Communications Societies. New York: IEEE Press 2003:702-711.
[11]LI Ning，HOU J C，SHA L.Design and analysis of an MST-based topology control algorithm[J]. IEEE Trans on Wireless Communications 2005，4(3):1195-1206.
[12]KARP B KUNG H T. GPSR:greedy perimeter stateless routing for wireless networks[C]//Proc of the 6th International Conference on Mobile Computing and Networking. New York: ACM Press，2000:243-254.
[13]LI Ning HOU J C. Topology control in heterogeneous wireless networks:problems and solutions[C]//Proc of IEEE Conference on Computer Communications. New York:IEEE Press 2004:232-243.
[14]NARAYANASWAMY S KAWADIA V SREENIVAS R S，et al. Power control in Ad hoc networks: theory architecture algorithm and implementation of the COMPOW protocol[C]//Proc of European Wireless Conference. 2002:156-162.
[15]BLOUGH D M LEONCINI M RESTA G，et al. The K-neigh protocol for symmetric topology control in Ad hoc networks[C]//Proc of the 4th ACM International Symposium on Mobile Ad hoc Networking and Computing. New York: ACM Press 2003.
[16]GUBA S KHULLER S. Approximation algorithms for connected dominating sets[J].Algorithmica，1998，20(4):374-387.
[17]DAS B BHARGHAVAN V. Routing in Ad hoc networks using minimum connected dominating set[C]//Proc of International Conference on Communication(ICC). 1997:376-380.
[18]DEB B BHATNAGAR S NATH B. A topology discovery algorithm for sensor networks with applications to network management DCS-TR-441[R].Comden NJ:Rutgers University 2001.
[19]HEINZELMAN W R CHANDRASAN A BALAKRISHNAN H. An application-specific protocol architecture for wireless micro-sensor networks[J]. IEEE Trans on Wireless Communications 2002，1(4):660-670.
[20]XU Ya HEIDEMANN J ESTRIN D. Geography-informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual International Conference on Mobile Computing and Networking. New York: ACM Press 2001:70-84.
[21]SANTI P SIMON J. Silence is golden with probability:maintaining a connected backbone in wireless sensor networks[C]//Proc ofthe 1st European Workshop on Wireless Sensor Networks. Berlin:Springer，2004:106-121.
[22]YOUNIS O FAHMY S. HEED: a hybrid energy-efficient distributed clustering approach for Ad hoc sensor networks[J].IEEE Trans on Mobile Computing，2004，3(4):660-669.
[23]KWON T J GERLA M. Clustering with power control[C]//Proc of the 4th IEEE Military Communications Conference. Atlantic City:IEEE Press，1999:1424-1428.
[24]CHIASSERINIC F CHLAMTAC I MONTI P et al.Energy efficient design of wireless Ad hoc networks[C]//Proc of the 2nd IFIP Networking Conference. London: Spring-Verlag 2002:376-386.
[25]KAWADIA V KUMAR P R. Power control and clustering in Ad hoc networks[C]//Proc of the 22nd Ammual Joint Conference on IEEE Computer and Communications Societies. New York: IEEE Press，2003:459-469.
[26]SCHURGERS C TSIATSIS V GANERIWAL S et al. Topology management for sensor networks: exploiting latency and density[C]//Proc of the 3rd ACM International Symposium on Mobile Ad hoc Networking Colllputing. New York: ACM Press 2002:135-145.
[27]CERPA A ESTRIN D. ASCENT: adaptive self-configuring sensor networks topologies[J].IEEE Trans on Mobile Computing 2004，3:272-285.
[28]TIAN Di GEORGANAS N D. A coverage-preserving node scheduling scheme for large wireless sensor networks[C]//Proc of the 1st ACM Workshop on Wireless Sensor Networks and Applications. New York: ACM Press 2002:32-41.
[29]SANTI P. Topology control in wireless Ad hoc and sensor networks[J].ACM Computing Surveys 2005，37(2):164-194.
[30]KAWADIA V KUMAR P R. A cautionary perspective on cross-layer design[J].IEEE Wireless Communications，2005，12(1):3-11.
收稿日期：2008-01-16；
修回日期：2008-03-24
基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(60704046 60725312)；遼寧省工業(yè)通信與控制系統(tǒng)重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目
作者簡(jiǎn)介：卞永釗（1976-），男，博士研究生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)管理、拓?fù)淇刂?bian_yz@sia.cn)；
于海斌（1964-），男，研究員，博導(dǎo)，主要研究方向?yàn)橹悄芸刂葡到y(tǒng)、網(wǎng)絡(luò)化技術(shù)等;
曾鵬（1976-），男，研究員，碩導(dǎo)，主要研究方向?yàn)閰f(xié)議工程、無(wú)線傳感器網(wǎng)絡(luò).
(1.中國(guó)科學(xué)院 沈陽(yáng)自動(dòng)化所 沈陽(yáng)110016; 2.中國(guó)科學(xué)院 研究生院 北京100039)
摘要：拓?fù)淇刂剖菬o(wú)線傳感器網(wǎng)絡(luò)研究中的核心問(wèn)題之一，它對(duì)于提高網(wǎng)絡(luò)生存周期、降低通信干擾、提高M(jìn)AC和路由協(xié)議、保證網(wǎng)絡(luò)連通和覆蓋質(zhì)量、提高網(wǎng)絡(luò)服務(wù)等具有重要意義。闡述了拓?fù)淇刂萍夹g(shù)研究的進(jìn)展，首先描述了拓?fù)淇刂萍捌浞椒ā⒃u(píng)價(jià)標(biāo)準(zhǔn)，然后從平面網(wǎng)絡(luò)、層次型網(wǎng)絡(luò)拓?fù)淇刂平榻B了一些代表性的研究工作，并指出了這些工作存在的不足，最后總結(jié)了研究現(xiàn)狀中存在的問(wèn)題以及拓?fù)淇刂蒲芯康陌l(fā)展方向。
關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò); 拓?fù)淇刂疲?功率控制； 支配集； 成簇算法
中圖分類(lèi)號(hào)：TP309
文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：1001-3695(2008)10-3128-06
Topology control for wireless sensor networks
BIAN Yong-zhao1，2 YU Hai-bin ZENG Peng1
(1.Shenyang Institute of Automation Chinese Academy of Sciences Shenyang 110016 China;
2.Graduate School Chinese Academy of-Sciences Beijing 100039 China)
Abstract:Topology control is one of the fundamental problems in wireless sensor networks. It is of great importance for prolonging network lifetime reducing radio interference increasing the efficiency of MAC and routing protocols ensure the-qua-lity of connecting and coverage increasing the network services and so on. This paper described the topology control problem and its methods criterion of estimation firstly then made an introduction of representative research efforts from two aspects homogeneous and non-homogeneous networks respectively and pointed out the defects of those efforts. Finally summarized existing problems open issues and research trends.
Key words：wirelss sensor networks(WSN); topology control; transmit power control; dominating set; clustering algorithm
0引言
無(wú)線傳感器網(wǎng)絡(luò)是一種新興的網(wǎng)絡(luò)，一般具有大規(guī)模、自組織、隨機(jī)部署、環(huán)境復(fù)雜、傳感器節(jié)點(diǎn)資源有限、網(wǎng)絡(luò)拓?fù)浣?jīng)常發(fā)生變化的特點(diǎn)[1]。無(wú)線傳感器網(wǎng)絡(luò)的這些特點(diǎn)決定了拓?fù)淇刂圃跓o(wú)線傳感器網(wǎng)絡(luò)研究中的重要作用，同時(shí)這些特點(diǎn)也使得它的拓?fù)淇刂蒲芯烤哂刑魬?zhàn)性。首先，拓?fù)淇刂剖且环N重要的節(jié)能技術(shù)；其次，拓?fù)淇刂票ＷC網(wǎng)絡(luò)覆蓋的質(zhì)量和連通質(zhì)量；另外拓?fù)淇刂颇軌蚪档屯ㄐ鸥蓴_、提高M(jìn)AC協(xié)議和路由協(xié)議的效率，為數(shù)據(jù)融合提供拓?fù)浠A(chǔ)；拓?fù)淇刂颇軌蛱岣呔W(wǎng)絡(luò)的容量、可靠性、可擴(kuò)展性等其他性能。總之拓?fù)淇刂茖?duì)網(wǎng)絡(luò)性能具有重大的影響，因而對(duì)它研究具有十分重要的意義。
本文提到的拓?fù)淇刂剖侵缚刂凭W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)由活動(dòng)節(jié)點(diǎn)的子集和進(jìn)行直接通信的活動(dòng)鏈路決定。拓?fù)淇刂扑惴ㄒ詧DG=(V，E)代表網(wǎng)絡(luò)。其中：V是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，當(dāng)且僅當(dāng)v1與v2之間有直接通信時(shí)，邊(v1，v2)∈EV2存在，將它變換到圖T＝(VT，ET)，可以得到VT∈V，ET∈E。
圖G代表原始網(wǎng)絡(luò)，為了能從圖G計(jì)算出變化后的圖T，拓?fù)淇刂扑惴ㄓ幸韵聨追N常用的方法：
a)減少活動(dòng)節(jié)點(diǎn)的數(shù)量(VTV)。例如可以利用網(wǎng)絡(luò)的冗余部署特性，周期性地關(guān)閉剩余能量較少的節(jié)點(diǎn)，激活其他節(jié)點(diǎn)來(lái)代替被關(guān)閉的節(jié)點(diǎn)。
b)可以控制活動(dòng)鏈路集或鄰節(jié)點(diǎn)集。如果無(wú)須使用網(wǎng)絡(luò)中的所有鏈路，那么可以剔除一些鏈路，將通信限制在重要鏈路中。
如果網(wǎng)絡(luò)是同構(gòu)的，即平面網(wǎng)絡(luò)，控制節(jié)點(diǎn)的鄰節(jié)點(diǎn)集只需不與某些節(jié)點(diǎn)通信即可。在無(wú)線傳感器網(wǎng)絡(luò)中選擇鄰節(jié)點(diǎn)最適合的方法就是控制節(jié)點(diǎn)的信號(hào)發(fā)射范圍，也就是采用功率控制或者采用自適應(yīng)的功率調(diào)整方法。圖1和2給出了原始的網(wǎng)絡(luò)拓?fù)浜凸β士刂浦蟮耐負(fù)浣Y(jié)構(gòu)。
拓?fù)淇刂埔部梢圆捎玫诙N方法，即重新安排活動(dòng)鏈路或鄰節(jié)點(diǎn)，形成一個(gè)層次型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并假設(shè)處于上層的節(jié)點(diǎn)具有特殊的功能。
如選擇某些節(jié)點(diǎn)作為骨干節(jié)點(diǎn)，只保持骨干節(jié)點(diǎn)之間的連接，其他節(jié)點(diǎn)的連接都指向骨干節(jié)點(diǎn)，所以骨干節(jié)點(diǎn)就形成了一個(gè)支配集(dominating set)：子集DV，V中的所有節(jié)點(diǎn)要么在D中，要么是節(jié)點(diǎn)d∈D的單跳鄰節(jié)點(diǎn)(v∈V:v∈D∨d∈D:(v，d)∈E)。支配集節(jié)點(diǎn)之間相互通信以及支配集與其鄰節(jié)點(diǎn)之間可以進(jìn)行通信，這樣能夠保證網(wǎng)絡(luò)的連通性。
另一種與支配集相關(guān)但略有不同的思想就是將網(wǎng)絡(luò)劃分成簇(clusters)。簇是包括原始網(wǎng)絡(luò)中所有節(jié)點(diǎn)的節(jié)點(diǎn)集的子集，每個(gè)簇中有簇首(cluster heads)，它是簇的代表，每個(gè)簇內(nèi)的節(jié)點(diǎn)距離簇首一般只有一跳。如果使簇的數(shù)量最小，就相當(dāng)于尋找最大獨(dú)立集(independent set)(存在子集CV，使v∈V-C:c∈C:(v，c)∈E，且C中沒(méi)有兩個(gè)節(jié)點(diǎn)在邊E-c1，c2∈C:(c1，c2)E上相交)。在這樣的分簇型的網(wǎng)絡(luò)中，簇首負(fù)責(zé)與簇內(nèi)節(jié)點(diǎn)之間的通信，同時(shí)簇間連接也是通過(guò)簇首的通信來(lái)實(shí)現(xiàn)的，這樣就可以保證整個(gè)網(wǎng)絡(luò)的連通性。圖3和4給出了采用骨干節(jié)點(diǎn)控制和簇結(jié)構(gòu)控制之后的拓?fù)浣Y(jié)構(gòu)。
1拓?fù)淇刂频脑u(píng)價(jià)標(biāo)準(zhǔn)
拓?fù)淇刂埔ＷC在一定的網(wǎng)絡(luò)連通質(zhì)量和覆蓋質(zhì)量的前提下，一般以延長(zhǎng)網(wǎng)絡(luò)生存周期為主要目標(biāo)，兼顧通信干擾、網(wǎng)絡(luò)延遲、負(fù)載均衡、可靠性、可擴(kuò)展性等其他性能，形成一個(gè)優(yōu)化的拓?fù)浣Y(jié)構(gòu)。無(wú)線傳感器網(wǎng)絡(luò)是與應(yīng)用相關(guān)的，不同的應(yīng)用其設(shè)計(jì)目標(biāo)不盡相同，采用的拓?fù)浣Y(jié)構(gòu)控制手段也不盡相同。以下提出一般拓?fù)淇刂扑惴ǖ膸讉€(gè)評(píng)價(jià)指標(biāo)。
1)連通性拓?fù)淇刂撇荒苁惯B通圖G變成非連通圖。也就是說(shuō)，如果G中的節(jié)點(diǎn)u與v之間有一條(可能是多跳)路徑，那么在T中也應(yīng)該有這樣一條路徑(顯然，不一定是同一條路徑)。如果至少要去掉k個(gè)節(jié)點(diǎn)才能使網(wǎng)絡(luò)不連通，那么就稱網(wǎng)絡(luò)是k-連通的，或者網(wǎng)絡(luò)的連通度為k。拓?fù)淇刂埔ＷC網(wǎng)絡(luò)是連通的(即至少1-連通)，這是拓?fù)淇刂频幕疽蟆＊?/p>
2）覆蓋率覆蓋率可以看成是對(duì)傳感器服務(wù)質(zhì)量的度量。覆蓋問(wèn)題可以分為區(qū)域覆蓋、點(diǎn)覆蓋和柵欄覆蓋[2]。區(qū)域覆蓋研究對(duì)目標(biāo)區(qū)域的覆蓋(監(jiān)測(cè))問(wèn)題；點(diǎn)覆蓋研究對(duì)一些離散的目標(biāo)點(diǎn)的覆蓋問(wèn)題；柵欄覆蓋研究運(yùn)動(dòng)物體穿越網(wǎng)絡(luò)部署區(qū)域被發(fā)現(xiàn)的概率問(wèn)題。相對(duì)而言，對(duì)區(qū)域覆蓋的研究較多。如果目標(biāo)區(qū)域中的任何一點(diǎn)都被k個(gè)傳感器節(jié)點(diǎn)監(jiān)測(cè)，就稱網(wǎng)絡(luò)是k-覆蓋的，或者稱網(wǎng)絡(luò)的覆蓋度為k。一般要求目標(biāo)區(qū)域的每一個(gè)點(diǎn)至少被一個(gè)節(jié)點(diǎn)監(jiān)測(cè)，即1-覆蓋。
3）吞吐量化簡(jiǎn)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)應(yīng)該能夠支持與原始網(wǎng)絡(luò)相似的通信量，尤其是在有大量突發(fā)事件時(shí)。設(shè)目標(biāo)區(qū)域是一個(gè)凸區(qū)域，每個(gè)節(jié)點(diǎn)的吞吐率為λ bps。在理想情況下有下面的關(guān)系式[3]：
λ≤(16AW/πΔ2L)(1/nr)bps
其中：A是目標(biāo)區(qū)域的面積；W是節(jié)點(diǎn)的最高傳輸速率；π是圓周率；Δ是大于0的常數(shù)；L是源節(jié)點(diǎn)到目的節(jié)點(diǎn)的平均距離；n是節(jié)點(diǎn)數(shù)；r是理想球狀無(wú)線電發(fā)射模型的發(fā)射半徑。由此可以看出，減小發(fā)射半徑或減小工作網(wǎng)絡(luò)的規(guī)模，在節(jié)省能量的同時(shí)可以在一定程度上提高網(wǎng)絡(luò)的吞吐能力。
4)魯棒性當(dāng)在原始圖G中的鄰近關(guān)系發(fā)生變化時(shí)(如節(jié)點(diǎn)運(yùn)動(dòng)、失效或無(wú)線信道特性發(fā)生變化)，一些節(jié)點(diǎn)的拓?fù)湫畔⒖赡軙?huì)發(fā)生變化。顯然魯棒的拓?fù)浣Y(jié)構(gòu)只需進(jìn)行少量的調(diào)整就可以避免對(duì)本地節(jié)點(diǎn)重新組織而造成整個(gè)網(wǎng)絡(luò)的波動(dòng)。
5）算法總開(kāi)銷(xiāo)對(duì)于資源有限的節(jié)點(diǎn)來(lái)說(shuō)，算法本身的開(kāi)銷(xiāo)應(yīng)該小一些，如附加信息少、計(jì)算量小；另外分布式實(shí)現(xiàn)也是一個(gè)必要條件。
在當(dāng)前的無(wú)線傳感器網(wǎng)絡(luò)中，連通性、覆蓋性和擴(kuò)展因子可能是除了必不可少的分布式性質(zhì)和低開(kāi)銷(xiāo)量之外的拓?fù)淇刂扑惴ㄗ钪匾奶匦浴３酥猓負(fù)淇刂七€要考慮網(wǎng)絡(luò)的生存周期、網(wǎng)絡(luò)中的干擾和競(jìng)爭(zhēng)、延遲、拓?fù)湫再|(zhì)、負(fù)載均衡等其他方面，拓?fù)淇刂频母鞣N設(shè)計(jì)目標(biāo)之間有著復(fù)雜的關(guān)系，這些關(guān)系也是拓?fù)淇刂蒲芯康闹匾獌?nèi)容。
2平面網(wǎng)絡(luò)中的拓?fù)淇刂啤β士刂篇?/p>
在平面網(wǎng)絡(luò)中，所有的節(jié)點(diǎn)都是同構(gòu)的，具有同樣的硬件、同樣的能力，完成同樣的任務(wù)。在平面網(wǎng)絡(luò)中拓?fù)淇刂谱罨镜姆椒ㄊ强刂婆c一個(gè)節(jié)點(diǎn)通信的鄰節(jié)點(diǎn)集。而這個(gè)問(wèn)題與控制節(jié)點(diǎn)的發(fā)射功率有著密切的關(guān)系，所以一般稱為功率控制。
目前，對(duì)平面網(wǎng)絡(luò)的拓?fù)淇刂蒲芯糠椒ㄖ饕譃閮深?lèi)：a)概率分析的方法，在節(jié)點(diǎn)按照某種概率密度分布的情況下，計(jì)算使拓?fù)錆M足某些性質(zhì)(一般是連通性、覆蓋率)所需要的最小發(fā)射功率和最小鄰節(jié)點(diǎn)個(gè)數(shù)；b)計(jì)算幾何方法，以某些幾何結(jié)構(gòu)為基礎(chǔ)構(gòu)建網(wǎng)絡(luò)拓?fù)洌詽M足某些性質(zhì)。
2.1概率分析方法
研究人員針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的特點(diǎn)提出了幾何隨機(jī)圖理論。假設(shè)網(wǎng)絡(luò)采用單位圓盤(pán)圖模型(unit disk graph，UDG)以及在給定面積為A的區(qū)域內(nèi)節(jié)點(diǎn)是均勻分布的，這個(gè)假設(shè)模型正好對(duì)應(yīng)于幾何隨機(jī)圖理論。
文獻(xiàn)[4]采用了一種基于幾何隨機(jī)圖的類(lèi)似算法來(lái)確定圖是k-連通的概率表達(dá)式，如果節(jié)點(diǎn)的發(fā)射功率大到足以保證圖的最小度數(shù)至少為k(概率很大)，那么有大量節(jié)點(diǎn)的圖就是k-連通的。Bettstetter利用這個(gè)結(jié)論推導(dǎo)出了一個(gè)圖中最小節(jié)點(diǎn)度的概率公式:
P(G是連通的) ≈1-∑k-1l=0(ρπr2)l/l!·e-ρπr2
(1)
其中：r為節(jié)點(diǎn)的發(fā)射半徑；ρ為節(jié)點(diǎn)的密度(假設(shè)節(jié)點(diǎn)在給定區(qū)域內(nèi)均勻分布)。
Li等人[5]也研究過(guò)k-連通問(wèn)題，提出了當(dāng)發(fā)射半徑r在k＞0時(shí)滿足nπr2≥ln n+(2k-1) ln ln n-2 ln k+2α且n足夠大時(shí)，節(jié)點(diǎn)數(shù)為n的網(wǎng)絡(luò)(k+1)連通的概率至少是ee-α。
如果網(wǎng)絡(luò)中的節(jié)點(diǎn)并不是均勻分布的，尤其是稀疏網(wǎng)絡(luò)，那么幾何隨機(jī)圖理論就無(wú)法應(yīng)用，但是研究人員對(duì)此也做了一些工作。Santi等人[6]假設(shè)n個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)數(shù)固定，也可能變化)在d維部署區(qū)域R＝[0，l]d內(nèi)隨機(jī)均勻部署，對(duì)于節(jié)點(diǎn)密度ρ=n/ld沒(méi)有限制，他們的目標(biāo)是使所有節(jié)點(diǎn)都具有最小半徑發(fā)射半徑r，使得到的圖是連通的。
對(duì)一維d=1的情況，可以證明，如果rn≥2l ln l，那么圖是連通的概率很高；如果rn≤l ln l，圖是非連通的概率很高。對(duì)于d=2，3的情況，給出了如下結(jié)論：
對(duì)于某常數(shù)k＞0，設(shè)rdl=kld ln l，r=r(l)＜＜l和n=n(l)＞＞1。如果k＞d×2d dd/2(或k=d×2ddd/2及r=r(l)＞＞1)，那么圖是連通的概率很高。
設(shè)r=r(l)＜＜l和n=n(l)＞＞1。如果f d∈O(ld)，那么圖是非連通的概率很高。
還有其他一些平面網(wǎng)絡(luò)的研究結(jié)果，Kubisch等人[7]描述了兩種將鄰節(jié)點(diǎn)數(shù)控制在一定數(shù)量?jī)?nèi)的分布式算法，并通過(guò)仿真實(shí)驗(yàn)評(píng)價(jià)了它們的性能。Liu等人[8]研究了關(guān)于節(jié)點(diǎn)有不同最大發(fā)射范圍的問(wèn)題，得到了非連接的信息，采用了一個(gè)分布式拓?fù)浣Y(jié)構(gòu)控制算法來(lái)最小化最大功率，保持了每個(gè)節(jié)點(diǎn)的可達(dá)性。Royer等人[9]研究了功率控制和移動(dòng)性的關(guān)系，功率控制與Ad hoc路由協(xié)議之間的相互作用，即Ad hoc按需距離矢量(AODV)的性能，證明了不存在最優(yōu)密度，但是密度會(huì)隨著節(jié)點(diǎn)的運(yùn)動(dòng)而增大。當(dāng)前大部分研究把功率控制看做與網(wǎng)絡(luò)中其他層是無(wú)關(guān)的。Cruz等人[10]研究了跨層問(wèn)題，提出了一個(gè)結(jié)合連接調(diào)度表和功率控制的算法。
2.2計(jì)算幾何方法
如果能夠獲得節(jié)點(diǎn)之間的距離或它們的相對(duì)位置的信息，那么可以有效地實(shí)現(xiàn)將網(wǎng)絡(luò)拓?fù)渥兊孟∈琛＠糜?jì)算幾何方法構(gòu)建鄰近圖的方法能夠?qū)崿F(xiàn)拓?fù)淇刂啤＝?jīng)常使用的幾何結(jié)構(gòu)有以下幾種：
a)最小生成樹(shù)(MST)。文獻(xiàn)[11]提出了一種基于本地信息的最小生成樹(shù)的構(gòu)造法，其思想是每個(gè)節(jié)點(diǎn)會(huì)收集它的鄰節(jié)點(diǎn)，然后構(gòu)造(如使用prim算法)這些節(jié)點(diǎn)的最小生成樹(shù)，將能量代價(jià)作為連接權(quán)重(代價(jià)相同的連接由加入的節(jié)點(diǎn)表示符作為間斷符來(lái)區(qū)分)。下一步的關(guān)鍵就是在化簡(jiǎn)后的拓?fù)渲斜Ａ暨@些對(duì)應(yīng)于最小生成樹(shù)中直接鄰節(jié)點(diǎn)的邊。這種構(gòu)造法保持了原圖的連通性，而且每個(gè)節(jié)點(diǎn)的最大度數(shù)是6。它能限制雙向連接，也比較容易加入功率控制。而且，平均節(jié)點(diǎn)度數(shù)比較小，接近理論界限。
b)Gabriel圖(Gabriel graph，GG)。在傳輸功率正比傳輸距離的平方時(shí)，GG是最節(jié)能的拓?fù)洹ST是GG的子圖，GG也滿足連通性。 在文獻(xiàn)[12]中介紹了GG的分布式構(gòu)造法。一個(gè)節(jié)點(diǎn)必須要對(duì)于它的所有鄰節(jié)點(diǎn)都測(cè)試邊的圈定義是否還成立，如果所有的節(jié)點(diǎn)都與它們的鄰節(jié)點(diǎn)的位置相交換，那么這是很容易做到的。
c)相關(guān)鄰近圖（relative neighbor graph，RNG），很容易用本地算法實(shí)現(xiàn)。如果原始圖G是連通的，那么它也是連通的。其稀疏程度在MST和GG之間，連通性也在MST和GG之間，優(yōu)于MST，沖突干擾優(yōu)于GG，是兩者的折中。RNG易于用分布式算法構(gòu)造。
Li等人[13]提出的DRNG和DLMST是兩個(gè)具有代表性的基于鄰近圖理論的算法。基于鄰近圖的功率控制算法的基本思想是：設(shè)所有節(jié)點(diǎn)都是用最大發(fā)射功率發(fā)射時(shí)形成的拓?fù)鋱DG，按照一定的鄰居判別條件求出該圖的鄰近圖G′，每個(gè)節(jié)點(diǎn)以自己所鄰近的最遠(yuǎn)節(jié)點(diǎn)來(lái)確定發(fā)射功率。DRNG是基于有向RNG的，DLMST是基于有向局部MST的。DRNG和DLMST能夠保證網(wǎng)絡(luò)的連通性，在平均功率和節(jié)點(diǎn)度等方面具有良好的性能。
平面網(wǎng)絡(luò)的功率控制算法除了上面兩類(lèi)基本類(lèi)型之外，研究人員也提出了一些其他算法，如分布式公共功率協(xié)議COMPOW[14]，K-NEIGH協(xié)議[15]等。
分布式公共功率協(xié)議COMPOW。簡(jiǎn)單地將功率控制與路由協(xié)議相結(jié)合的解決方案。其基本思想是：所有的傳感器節(jié)點(diǎn)使用同樣的發(fā)射功率，在保證網(wǎng)絡(luò)連通的前提下，將功率最小化。COMPOW在各個(gè)功率層上建立路由表，在功率Pi層上，通過(guò)使用功率Pi交換HELLO消息建立路由表RTPi，所有可達(dá)節(jié)點(diǎn)都是路由表中的表項(xiàng)。COMPOW選擇最小的發(fā)射功率Pcom，使得RTPcow和RTPmax具有相同的表項(xiàng)。其中Pmax是最大發(fā)射功率。于是整個(gè)網(wǎng)絡(luò)都使用公共的發(fā)射功率Pcom。在節(jié)點(diǎn)分布均勻的情況下，COMPOW具有較好的性能，但是一個(gè)相對(duì)孤立的節(jié)點(diǎn)會(huì)導(dǎo)致所有的節(jié)點(diǎn)使用很大的發(fā)射功率。另外這個(gè)理論雖然實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，但是它需要保留所有潛在節(jié)點(diǎn)的路由表，這一點(diǎn)使得它基本上不適合無(wú)線傳感器網(wǎng)絡(luò)。
K-NEIGH協(xié)議的思想是使每個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)數(shù)保持k個(gè)或接近于k個(gè)。這個(gè)協(xié)議是分布式的，基于節(jié)點(diǎn)間的距離是估計(jì)的，而且需要總量為2｜V｜的信息交換量。這種方法是節(jié)點(diǎn)用大發(fā)射功率發(fā)布它們的信標(biāo)，收集它們觀察到的鄰節(jié)點(diǎn)的信息，按距離對(duì)鄰節(jié)點(diǎn)進(jìn)行分類(lèi)，并計(jì)算能夠互相到達(dá)的k個(gè)最近的鄰節(jié)點(diǎn)，這樣每個(gè)節(jié)點(diǎn)用最小的發(fā)射功率就能到達(dá)剛才計(jì)算的所有鄰節(jié)點(diǎn)。在這個(gè)協(xié)議的設(shè)計(jì)中，需要注意的是要等待足夠長(zhǎng)的時(shí)間隨機(jī)地喚醒節(jié)點(diǎn)，以及適當(dāng)解決潛在的非對(duì)稱鏈路的問(wèn)題。
3層次型網(wǎng)絡(luò)中的拓?fù)淇刂平Y(jié)構(gòu)
研究無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的另一種方法是在網(wǎng)絡(luò)節(jié)點(diǎn)中形成一種層次關(guān)系，構(gòu)成一個(gè)層次型的網(wǎng)絡(luò)。目前主要有兩種研究手段，即采用支配集的層次型網(wǎng)絡(luò)和采用分簇結(jié)構(gòu)的層次型網(wǎng)絡(luò)。
3.1采用支配集的層次型網(wǎng)絡(luò)
在網(wǎng)絡(luò)中選出一些虛擬骨干節(jié)點(diǎn)組成虛擬骨干網(wǎng)，這些節(jié)點(diǎn)又叫做支配集，即如果V中所有節(jié)點(diǎn)或在D中，或是某個(gè)節(jié)點(diǎn)d∈D的單跳鄰節(jié)點(diǎn)(v∈V:v∈D∨d∈D:(v，d)∈E)，這里D就是支配集。而這個(gè)支配集在某種程度上應(yīng)該盡量小，這也是最小支配集問(wèn)題(minimum dominating set，MDS)。
文獻(xiàn)[16]介紹了兩種集中式的例子。a)生成樹(shù)結(jié)構(gòu)。主要思想是像生成樹(shù)型結(jié)構(gòu)一樣構(gòu)造支配集，迭代地給樹(shù)加入舊節(jié)點(diǎn)和邊，直到所有的舊節(jié)點(diǎn)都被覆蓋為止。這個(gè)算法用節(jié)點(diǎn)的顏色來(lái)表示：白色節(jié)點(diǎn)表示沒(méi)有被處理，黑色節(jié)點(diǎn)屬于支配集，灰色節(jié)點(diǎn)表示受控集。b)先構(gòu)造一個(gè)不一定連通的支配集，然后在下一個(gè)階段，把集合內(nèi)的所有節(jié)點(diǎn)連接在一起。把非連通的支配集連通起來(lái)也叫做尋找斯坦納樹(shù)(Steiner tree)問(wèn)題。
生成樹(shù)的分布式算法可以由文獻(xiàn)[17]介紹的分布式算法來(lái)實(shí)現(xiàn)。從本質(zhì)上來(lái)說(shuō)，就是所有灰色節(jié)點(diǎn)發(fā)現(xiàn)它們的兩跳鄰節(jié)點(diǎn)，并確定每個(gè)節(jié)點(diǎn)能夠得到的最大收益，然后分布式地選擇最大收益，就可以確定下一個(gè)黑色節(jié)點(diǎn)了。
TopDisc(topology discovery)算法[18]來(lái)源于圖論的思想，是基于最小支配集問(wèn)題的經(jīng)典算法。它利用顏色區(qū)分節(jié)點(diǎn)狀態(tài)，解決骨干網(wǎng)拓?fù)浣Y(jié)構(gòu)的形成問(wèn)題。在TopDisc 算法中，由網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)啟動(dòng)發(fā)送用于發(fā)現(xiàn)鄰節(jié)點(diǎn)的查詢消息，查詢消息攜帶發(fā)送節(jié)點(diǎn)的狀態(tài)信息。隨著查詢消息在網(wǎng)絡(luò)中傳播，TopDisc 算法依次為每個(gè)節(jié)點(diǎn)標(biāo)記顏色。最后，按照節(jié)點(diǎn)顏色區(qū)分出骨干網(wǎng)節(jié)點(diǎn)，并通過(guò)反向?qū)ふ也樵兿⒌膫鞑ヂ窂皆诠歉删W(wǎng)節(jié)點(diǎn)之間建立通信鏈路。每個(gè)骨干網(wǎng)節(jié)點(diǎn)管理與自己相鄰的普通節(jié)點(diǎn)。
TopDisc 算法中提出了兩種具體的節(jié)點(diǎn)狀態(tài)標(biāo)記辦法，分別稱為三色算法和四色算法。這兩種算法的區(qū)別在于尋找骨干網(wǎng)節(jié)點(diǎn)的標(biāo)準(zhǔn)不一樣，所以最后形成的拓?fù)浣Y(jié)構(gòu)也有所不同。
3.2采用簇結(jié)構(gòu)的層次型結(jié)構(gòu)
前面介紹了通過(guò)把一些節(jié)點(diǎn)作為骨干節(jié)點(diǎn)形成支配集，把層次結(jié)構(gòu)引入了網(wǎng)絡(luò)。另一種形成層次結(jié)構(gòu)的想法是把一些節(jié)點(diǎn)標(biāo)記為具有特殊的功能，如控制其鄰節(jié)點(diǎn)等，這樣就形成了簇，這個(gè)具有特殊功能的節(jié)點(diǎn)就叫做簇首。這種分簇方法的優(yōu)點(diǎn)與骨干節(jié)點(diǎn)類(lèi)似，但是更著重于本地資源的優(yōu)化使用，能夠屏蔽網(wǎng)絡(luò)高層的動(dòng)態(tài)特性，使高層協(xié)議更具有可擴(kuò)展性，另外簇首還能夠進(jìn)行本地?cái)?shù)據(jù)融合、壓縮任務(wù)。
LEACH(low energy adaptive clustering hierarchy)[19]算法是一種自適應(yīng)分簇算法，它的執(zhí)行過(guò)程是周期性的，每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。在簇的建立階段，相鄰節(jié)點(diǎn)動(dòng)態(tài)地形成簇，隨機(jī)產(chǎn)生簇首；在數(shù)據(jù)通信階段，簇內(nèi)節(jié)點(diǎn)把數(shù)據(jù)發(fā)送給簇首，簇首進(jìn)行數(shù)據(jù)融合并把結(jié)果發(fā)送給匯聚節(jié)點(diǎn)。由于簇首需要完成數(shù)據(jù)融合、與匯聚節(jié)點(diǎn)通信等工作，能量消耗大，LEACH算法能夠保證各節(jié)點(diǎn)等概率地?fù)?dān)任簇首，使得網(wǎng)絡(luò)中的節(jié)點(diǎn)相對(duì)均衡地消耗能量。
GAF算法[20]是基于地理位置的拓?fù)渌惴ǎ撬鼪](méi)有考慮節(jié)點(diǎn)的剩余能量，而是隨機(jī)地選擇節(jié)點(diǎn)作為簇首。該算法中的簇首承擔(dān)更多的數(shù)據(jù)處理和通信任務(wù)，消耗的能量相對(duì)較大，因此，簇首應(yīng)該選擇剩余能量較多的節(jié)點(diǎn)。P.Santi等人[21]提出了一種GAF改進(jìn)算法，他設(shè)計(jì)了兩種不同的簇首選擇機(jī)制，并詳細(xì)分析了簇首節(jié)點(diǎn)產(chǎn)生后的網(wǎng)絡(luò)運(yùn)行方式，同時(shí)驗(yàn)證了改進(jìn)的GAF算法對(duì)網(wǎng)絡(luò)生存時(shí)間的影響。與GAF算法相比，GAF改進(jìn)算法除了要求每個(gè)節(jié)點(diǎn)知道自己的ID以及屬于哪個(gè)單元格外，還要求同一單元格中的節(jié)點(diǎn)保持時(shí)間同步。GAF改進(jìn)算法有兩種簇首選擇機(jī)制，即完全型簇首選擇算法和隨機(jī)型簇首選擇算法。虛擬單元格建立起來(lái)后，每個(gè)節(jié)點(diǎn)都知道自己所屬的虛擬單元格。節(jié)點(diǎn)根據(jù)已知本單元格相關(guān)信息的多少?zèng)Q定采取哪種簇首節(jié)點(diǎn)選擇機(jī)制。
HEED[22]的基本思想是：根據(jù)對(duì)作為第一因素的剩余能量和作為第二因素的簇內(nèi)通信代價(jià)的綜合考慮，周期性地通過(guò)迭代的辦法實(shí)現(xiàn)分簇。HEED用最小平均可達(dá)功率(AMRP)作為當(dāng)某個(gè)節(jié)點(diǎn)被選為簇首時(shí)的簇內(nèi)通信代價(jià)的度量。
HEED不依賴于網(wǎng)絡(luò)的規(guī)模，通過(guò)O(1)次迭代實(shí)現(xiàn)分簇。迭代每一步的時(shí)間要足夠長(zhǎng)，使得節(jié)點(diǎn)能夠收到來(lái)自鄰節(jié)點(diǎn)的消息。初始時(shí)，每個(gè)節(jié)點(diǎn)要確定在一跳范圍內(nèi)的鄰節(jié)點(diǎn)的集合，計(jì)算并廣播AMRP，計(jì)算自己成為臨時(shí)簇首的初始概率CHp。
HEED綜合考慮了生存時(shí)間、可擴(kuò)展性和負(fù)載均衡，對(duì)節(jié)點(diǎn)的分布和能力也沒(méi)有特殊要求，雖然HEED的執(zhí)行并不依賴于同步，但是不同步卻會(huì)嚴(yán)重影響分簇的質(zhì)量。
4層次型拓?fù)浣Y(jié)構(gòu)與功率控制相結(jié)合
層次型方法(骨干網(wǎng)節(jié)點(diǎn)控制、成簇控制)和平面網(wǎng)絡(luò)中功率控制都是影響無(wú)線網(wǎng)絡(luò)拓?fù)涞挠行Х椒ā，F(xiàn)在的一個(gè)研究方向就是將這兩種機(jī)制結(jié)合在一起。
1)基于引導(dǎo)信號(hào)的功率控制[23]
這是一種早期的方法，簇首用這種方法來(lái)進(jìn)行功率控制，與在蜂窩網(wǎng)絡(luò)中進(jìn)行的功率控制相類(lèi)似。在建立初始的分簇結(jié)構(gòu)之后，簇首在引導(dǎo)信號(hào)和數(shù)據(jù)通信中使用功率控制。如果基于這些引導(dǎo)信號(hào)，所有節(jié)點(diǎn)都加入了同一個(gè)簇，那么就可以使用引導(dǎo)信號(hào)功率控制來(lái)控制簇的成員。數(shù)據(jù)通信功率控制用于保證遠(yuǎn)處節(jié)點(diǎn)的誤碼率足夠低以及對(duì)附近節(jié)點(diǎn)能高效地發(fā)送信息；它也能防止出現(xiàn)非常差的發(fā)射條件。功率控制的主要優(yōu)點(diǎn)是它在簇首中是集中式的，這簡(jiǎn)化了完全分布式的功率控制問(wèn)題。
2)Ad hoc網(wǎng)絡(luò)設(shè)計(jì)算法
Ad hoc網(wǎng)絡(luò)設(shè)計(jì)算法(Ad hoc network design algorithm，ANDA)[24]允許簇首通過(guò)功率控制來(lái)控制簇的大小，并且導(dǎo)出了一些具體的規(guī)則以盡可能延長(zhǎng)網(wǎng)絡(luò)的生存期。假設(shè)網(wǎng)絡(luò)的生存期主要由簇首決定，因?yàn)榇厥棕?fù)責(zé)收集、轉(zhuǎn)發(fā)感知信息，完成最主要的任務(wù)，能量消耗應(yīng)該在簇首間均衡。
這個(gè)方法的基本假設(shè)是:a)普通節(jié)點(diǎn)和(預(yù)選出的)簇首的位置是已知的；b)通信量在普通節(jié)點(diǎn)間均勻分布；c)簇首的生存期與它的初始能量成正比，與crα+dn成反比。其中：r是簇首覆蓋區(qū)域的半徑；n是簇內(nèi)成員的個(gè)數(shù)；α是路徑損耗系數(shù)；c、d是常數(shù)。算法的最佳目標(biāo)是使所有簇首的生存期最長(zhǎng)，或者相應(yīng)地使簇首中的最小生存期最長(zhǎng)。
這種求最大值的問(wèn)題是一個(gè)優(yōu)化問(wèn)題，用決策變量來(lái)描述簇j中普通節(jié)點(diǎn)i的成員身份。其中也隱含著所需的發(fā)射半徑。對(duì)于靜態(tài)網(wǎng)絡(luò)來(lái)說(shuō)，用一個(gè)簡(jiǎn)單的貪婪算法就能求得最優(yōu)解：將節(jié)點(diǎn)i分配給有最長(zhǎng)生存期的簇首，對(duì)所有節(jié)點(diǎn)重復(fù)這一操作。對(duì)于動(dòng)態(tài)網(wǎng)絡(luò)來(lái)說(shuō)，需要一個(gè)額外的重新配置過(guò)程，而且無(wú)法保證求得的是最優(yōu)解，但其實(shí)際性能還不錯(cuò)。
3)CLUSTERPOW
前面討論了在節(jié)點(diǎn)分布均勻的情況下，COMPOW算法具有較好的性能，但是，一個(gè)相對(duì)孤立的節(jié)點(diǎn)會(huì)導(dǎo)致所有的節(jié)點(diǎn)使用很大的發(fā)射功率，所以在節(jié)點(diǎn)分布不均勻的情況下，它的缺點(diǎn)是明顯的。針對(duì)這種缺點(diǎn)，改進(jìn)了COMPOW協(xié)議，提出了CLUSTERPOW協(xié)議[25]。它的基本思想是簡(jiǎn)單地假設(shè)一組離散的發(fā)射功率值，如1、10、100 mW。在每個(gè)功率值處，簇都是獨(dú)立形成的，而且對(duì)于每個(gè)功率值都有單獨(dú)的路由表。如果用最小功率就能保證到達(dá)目的節(jié)點(diǎn)，那么就發(fā)送數(shù)據(jù)，一旦數(shù)據(jù)進(jìn)入了包含目的節(jié)點(diǎn)的最小功率簇后，功率值就會(huì)被降低。在CLUSTERPOW中，分簇是隱含的，且無(wú)須任何簇首節(jié)點(diǎn)，分簇通過(guò)給定功率層的可達(dá)性來(lái)實(shí)現(xiàn)，分簇的層次由功率的層次數(shù)來(lái)實(shí)現(xiàn)，分簇是動(dòng)態(tài)的、分布的。
對(duì)較大的初始發(fā)射功率進(jìn)行替換是很有用的。為了實(shí)現(xiàn)這個(gè)目標(biāo)，在相關(guān)文獻(xiàn)中也描述了隧道式CLUSTERPOW協(xié)議。在這種情況下，為了避免無(wú)限地路由循環(huán)，必須將用于以最小功率進(jìn)行路由的中間節(jié)點(diǎn)的地址也裝入數(shù)據(jù)分組中。
5其他一些啟發(fā)式算法
還有一些其他的拓?fù)淇刂扑惴ǎ⒉皇菄?yán)格地符合利用骨干節(jié)點(diǎn)/支配集計(jì)算或分簇原理的，它們都是通過(guò)打開(kāi)或關(guān)閉某些節(jié)點(diǎn)來(lái)影響圖的拓?fù)浣Y(jié)構(gòu)。顯然，源節(jié)點(diǎn)和數(shù)據(jù)匯聚節(jié)點(diǎn)總是活動(dòng)的。
1)基于地理位置的拓?fù)渌惴?GAF)
Xu等人在文獻(xiàn)[20]中提出了基于地理位置的拓?fù)渌惴ǎ乃枷胧菍^(qū)域分成非常小的矩形，使每個(gè)矩形中的節(jié)點(diǎn)都能與相鄰矩形中的節(jié)點(diǎn)進(jìn)行通信。如果某些節(jié)點(diǎn)滿足某些條件，那么這些節(jié)點(diǎn)從網(wǎng)絡(luò)的高層(如路由層)來(lái)看可以看做是等價(jià)的。當(dāng)一個(gè)節(jié)點(diǎn)休眠時(shí)，可以激活它的等價(jià)節(jié)點(diǎn)來(lái)替代。
假設(shè)節(jié)點(diǎn)都知道它們自己的位置，所以這些節(jié)點(diǎn)能很容易地構(gòu)成這樣的等效矩形，并在它們自己的矩形中確定節(jié)點(diǎn)。這些節(jié)點(diǎn)之間互相合作確定休眠模式，按順序參加路由協(xié)議。Xu等人證明了使用這種方案，Ad hoc路由協(xié)議的能量效率能被提高40％～60％。
2)STEM算法
在GAF(或其他有等價(jià)節(jié)點(diǎn)概念的方法)的基礎(chǔ)上，可以加入稀疏拓?fù)浜湍芰抗芾?sparse topology and energy management)協(xié)議[26]。
STEM是節(jié)點(diǎn)喚醒算法，在STEM算法中，節(jié)點(diǎn)需要采用一種簡(jiǎn)單而迅速的節(jié)點(diǎn)喚醒方式，保證網(wǎng)絡(luò)通信的暢通和較小的延遲。該算法又包括兩種不同的機(jī)制，即STEM-B和STEM-T。它使節(jié)點(diǎn)在整個(gè)生命周期中大多數(shù)時(shí)間內(nèi)處于睡眠狀態(tài)。節(jié)點(diǎn)的睡眠周期、部署密度以及網(wǎng)絡(luò)的傳輸延遲之間有著密切的關(guān)系。GAF關(guān)閉節(jié)點(diǎn)，但是卻保持網(wǎng)絡(luò)的轉(zhuǎn)發(fā)容量；虛擬喚醒信道的STEM機(jī)制提高了能量效率，卻也增大了路徑建立的延遲。Schurgers等人[26]建議將這兩種方法結(jié)合起來(lái)，即把STEM算法應(yīng)用于GAF算法中等價(jià)的節(jié)點(diǎn)集合之中。
3)可變的自適應(yīng)拓?fù)渌惴?ASCENT)
加州大學(xué)洛杉磯分校的Cerpa等人[27]提出了一種著重于保證數(shù)據(jù)通路暢通的ASCENT算法。保留一定數(shù)量的節(jié)點(diǎn)作為路由節(jié)點(diǎn)，其余節(jié)點(diǎn)轉(zhuǎn)入休眠狀態(tài)，但是節(jié)點(diǎn)不僅根據(jù)附近節(jié)點(diǎn)的通信量來(lái)確定是否成為活動(dòng)節(jié)點(diǎn)，還要考慮丟包率指標(biāo)。如果某個(gè)節(jié)點(diǎn)發(fā)現(xiàn)丟包嚴(yán)重，就向鄰節(jié)點(diǎn)發(fā)出求救信息；收到求救信息的節(jié)點(diǎn)主動(dòng)成為工作節(jié)點(diǎn)，幫助鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包。但是，ASCENT并不能保證網(wǎng)絡(luò)的連通性，因?yàn)樗皇峭ㄟ^(guò)丟包率來(lái)判斷連通性的。事實(shí)上，當(dāng)網(wǎng)絡(luò)不連通時(shí)，它是無(wú)法檢測(cè)和修復(fù)的。ASCENT也不能保證能量的均勻消耗。
節(jié)點(diǎn)可以關(guān)閉自己，但是必須周期性地進(jìn)入被動(dòng)狀態(tài)來(lái)監(jiān)聽(tīng)?zhēng)椭?qǐng)求。對(duì)網(wǎng)絡(luò)性能的監(jiān)測(cè)依賴于拓?fù)淇刂疲@是ASCENT算法區(qū)別于其他算法的地方，但是，它有大量需要優(yōu)化的參數(shù)。
4)在傳感器覆蓋率的基礎(chǔ)上關(guān)閉節(jié)點(diǎn)
與傳統(tǒng)的Ad hoc網(wǎng)絡(luò)不同的是，對(duì)WSN來(lái)說(shuō)，只保證網(wǎng)絡(luò)的連通性是不夠的。WSN的主要任務(wù)是感知和測(cè)量它周?chē)沫h(huán)境。為了完成這項(xiàng)任務(wù)，無(wú)論是否需要連通性(可能是弱連通的)，觀測(cè)區(qū)域都必須被足夠多的節(jié)點(diǎn)覆蓋。通常，WSN的感測(cè)覆蓋率問(wèn)題是一個(gè)很難解決的問(wèn)題。
Tian等人[28]指出要關(guān)閉節(jié)點(diǎn)，就必須保證節(jié)點(diǎn)的感測(cè)覆蓋區(qū)域會(huì)由其他節(jié)點(diǎn)覆蓋。只有這樣的節(jié)點(diǎn)才有資格休眠一段時(shí)間。
假設(shè)節(jié)點(diǎn)知道它們的位置和它們的感測(cè)區(qū)域，在與它們的鄰節(jié)點(diǎn)交換信息后(如在循環(huán)的開(kāi)始)，節(jié)點(diǎn)確定它自己的感測(cè)區(qū)域是否被它的鄰節(jié)點(diǎn)所覆蓋，這只是一個(gè)簡(jiǎn)單的地理問(wèn)題。如果是，節(jié)點(diǎn)就聲明它可以休眠，并通知它的鄰節(jié)點(diǎn)，然后進(jìn)入休眠狀態(tài)。
如果所有可以休眠的節(jié)點(diǎn)同時(shí)進(jìn)入休眠狀態(tài)并立即關(guān)閉自己，就有出現(xiàn)盲點(diǎn)的危險(xiǎn)。如果兩個(gè)鄰節(jié)點(diǎn)均可以休眠，根據(jù)假設(shè)，它們認(rèn)為另一個(gè)節(jié)點(diǎn)會(huì)保持活動(dòng)(在另一邊剩余的未覆蓋區(qū)域會(huì)由其他更遠(yuǎn)的節(jié)點(diǎn)覆蓋)，就會(huì)發(fā)生這種情況。為了避免這種情況，休眠資格的通告是用通用的隨機(jī)補(bǔ)償算法進(jìn)行隨機(jī)延遲的。當(dāng)節(jié)點(diǎn)接收到這樣的信息時(shí)，它從它的鄰節(jié)點(diǎn)列表中將這個(gè)很快要進(jìn)入休眠狀態(tài)的節(jié)點(diǎn)刪除，并重新評(píng)估它自己的休眠資格。
這個(gè)算法基于節(jié)點(diǎn)是冗余部署這一事實(shí)的；否則不可能有節(jié)點(diǎn)可以休眠。這是一個(gè)簡(jiǎn)單而有效的方法，并且考慮了WSN的實(shí)際特性。
6存在的問(wèn)題及進(jìn)一步需要研究的內(nèi)容
上面總結(jié)了當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯恐凶罹叽硇缘墓ぷ鳎瑫r(shí)也指出了存在的問(wèn)題。
1)拓?fù)淇刂贫x問(wèn)題
現(xiàn)在對(duì)拓?fù)淇刂七€沒(méi)有一個(gè)清晰的定義，在文獻(xiàn)[29]中，P.Santi提出了一個(gè)非正式的定義：拓?fù)淇刂剖菫榱松梢粋€(gè)具有某種屬性(如連通性)的網(wǎng)絡(luò)，協(xié)調(diào)網(wǎng)絡(luò)中的節(jié)點(diǎn)決定它們傳輸范圍的一種技術(shù)，同時(shí)能夠減少節(jié)點(diǎn)的能量消耗和(或)增加網(wǎng)絡(luò)的容量。作者區(qū)分了一般的節(jié)點(diǎn)節(jié)能技術(shù)、節(jié)點(diǎn)功率控制技術(shù)和拓?fù)淇刂萍夹g(shù)的區(qū)別，同時(shí)又認(rèn)為成簇技術(shù)是控制網(wǎng)絡(luò)拓?fù)涞囊环N手段，因?yàn)槌纱剡^(guò)程中節(jié)點(diǎn)的發(fā)射功率是固定的，所以成簇技術(shù)并不是一種拓?fù)淇刂萍夹g(shù)。現(xiàn)在大多數(shù)人認(rèn)為拓?fù)淇刂萍夹g(shù)是在保證一定的網(wǎng)絡(luò)屬性(如連通性、覆蓋性等)的前提下，以延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間為目標(biāo)，采用各種技術(shù)使網(wǎng)絡(luò)形成一個(gè)優(yōu)化的網(wǎng)絡(luò)拓?fù)洌β士刂坪蛯哟涡途W(wǎng)絡(luò)控制都是手段。但是如何衡量是優(yōu)化的網(wǎng)絡(luò)呢？度量網(wǎng)絡(luò)的性能指標(biāo)是什么？目前平面網(wǎng)絡(luò)的功率控制以及層次型網(wǎng)絡(luò)控制的研究一般都是獨(dú)立進(jìn)行的，不同的應(yīng)用可能有不同的優(yōu)化目標(biāo)，性能指標(biāo)也不同，不太可能給出一個(gè)通用的定義。
2)拓?fù)淇刂圃趨f(xié)議棧中的位置
拓?fù)淇刂婆c協(xié)議棧的其他層關(guān)系密切，與物理層、鏈路層、網(wǎng)絡(luò)層和傳輸層交互作用。由于無(wú)線傳感器網(wǎng)絡(luò)中的協(xié)議棧中的各層之間的界限也已經(jīng)模糊，那么拓?fù)淇刂频降孜挥谀囊粚樱總鹘y(tǒng)認(rèn)為[29]拓?fù)淇刂莆挥贛AC層之上、路由層之下，它與路由層、MAC層之間的關(guān)系最為密切；但是也有人認(rèn)為拓?fù)淇刂品稚⒃诟鲗覽30]，所有這些都給協(xié)議棧設(shè)計(jì)帶來(lái)了困難。因此拓?fù)淇刂婆cMAC、路由、數(shù)據(jù)融合、數(shù)據(jù)存儲(chǔ)以及數(shù)據(jù)傳輸?shù)绕渌矫娼Y(jié)合的研究極大拓寬了拓?fù)淇刂频难芯款I(lǐng)域。
3)缺乏對(duì)拓?fù)淇刂扑惴ǖ挠行Ф攘开?/p>
拓?fù)淇刂埔岣呔W(wǎng)絡(luò)的各種性能，包括覆蓋質(zhì)量、能量消耗、連通質(zhì)量、干擾、延時(shí)、魯棒性等。但是目前還沒(méi)有對(duì)這些性能的有效度量的方法。一個(gè)實(shí)用的拓?fù)淇刂萍夹g(shù)其實(shí)應(yīng)該綜合考慮這些性能指標(biāo)，但到目前為止還沒(méi)有這樣的研究。有人提出了網(wǎng)絡(luò)生存周期，但是網(wǎng)絡(luò)生存周期沒(méi)有一個(gè)統(tǒng)一的定義，實(shí)際上網(wǎng)絡(luò)生存周期是一個(gè)綜合的抽象的性能指標(biāo)。如何有效地度量網(wǎng)絡(luò)的性能，也就是如何有效度量控制算法的性能，這些也是拓?fù)淇刂埔芯康膬?nèi)容。
由此看來(lái)，無(wú)線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂七€有很多問(wèn)題需要研究，這些問(wèn)題構(gòu)成了拓?fù)淇刂蒲芯康膬?nèi)容，這些研究?jī)?nèi)容之間又是相互制約、密不可分的。
7結(jié)束語(yǔ)
本文簡(jiǎn)要地描述了無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂频难芯楷F(xiàn)狀以及其中存在的一些問(wèn)題。現(xiàn)在拓?fù)淇刂蒲芯康陌l(fā)展趨勢(shì)是以實(shí)際應(yīng)用為背景，多種機(jī)制結(jié)合使用，強(qiáng)調(diào)網(wǎng)絡(luò)拓?fù)淇刂频淖赃m應(yīng)性和魯棒性，在保證網(wǎng)絡(luò)連通性和覆蓋度的前提下，提高網(wǎng)絡(luò)的通信效率，最大限度地節(jié)省能量來(lái)延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存時(shí)間。但是目前的研究還普遍存在著模型過(guò)于理想化，對(duì)網(wǎng)絡(luò)性能的綜合考慮比較少，研究結(jié)果缺乏足夠的說(shuō)服力，沒(méi)有考慮實(shí)際應(yīng)用中的困難。拓?fù)淇刂七€有許多問(wèn)題有待進(jìn)一步研究，特別是要根據(jù)實(shí)際應(yīng)用情況探索更加實(shí)用的拓?fù)淇刂萍夹g(shù)。以實(shí)際應(yīng)用為背景、多種機(jī)制相結(jié)合、綜合考慮網(wǎng)絡(luò)各種性能將是拓?fù)淇刂蒲芯康陌l(fā)展趨勢(shì)。
參考文獻(xiàn)：
[1]AKYILDIZ I F SU W SANKARASUBRAMANIAS Y，et al.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8):102-114.
[2]THAI M T WANG F DU D Z. Coverage problems in wireless sensor networks:designs and analysis[J].International Journal of Sensor Networks 2008，3(3):191-200.
[3]GUPTA P KUMAR P R. The capacity of wireless networks[J].IEEE Trans on Information Theory，2000，46(2):388-404.
[4]BETTSTETTER C. On the minimum node degree and connectivity of a wireless multihop network[M]. Los Alamitos: IEEE Computer Society Press，2002:80-91.
[5]LI Xiang-yang WAN Peng-jun WANG Yu et al. Fault tolerant deployment and topology control in wireless networks[C]//Proc of the 4th ACM Symposium on Mobile Ad hoc Networking and Computing. New York:ACM Press，2003:117-128.
[6]SANTI P BLOUGH D M. The critical transmitting range for connectivity in sparse wireless Ad hoc networks[J].IEEE Trans on Mobile Computing 2003，2(1):25-39.
[7]KUBISCH M KARL H WOLISZ A，et al. Distributed algorithms for transmission power control in wireless sensor networks[C]//Proc of IEEE Wireless Communications and Networking(WCNC).New York: IEEE Press 2003:558-563.
[8]LIU Ji-lei LI Bao-chun. Distributed topology control in wireless sensor networks with asymmetric links[C]//Proc of IEEE Globecom Wireless Communications Symposium. San Francisco:[s.n.] 2003.
[9]ROYER E M，MELLIAR-SMITH P M，MOSER L E.An analysis of the optimum node density for Ad hoc mobile networks[C]//Proc of IEEE International Conference on Communications.Helsinki:[s.n.] 2001:857-861.
[10]CRUZ R L SANTHANAM A V. Optimal routing link scheduling and power control in multi-hop wireless networks[C]//Proc of the 22nd Annual Joint Conference on IEEE Computer and Communications Societies. New York: IEEE Press 2003:702-711.
[11]LI Ning，HOU J C，SHA L.Design and analysis of an MST-based topology control algorithm[J]. IEEE Trans on Wireless Communications 2005，4(3):1195-1206.
[12]KARP B KUNG H T. GPSR:greedy perimeter stateless routing for wireless networks[C]//Proc of the 6th International Conference on Mobile Computing and Networking. New York: ACM Press，2000:243-254.
[13]LI Ning HOU J C. Topology control in heterogeneous wireless networks:problems and solutions[C]//Proc of IEEE Conference on Computer Communications. New York:IEEE Press 2004:232-243.
[14]NARAYANASWAMY S KAWADIA V SREENIVAS R S，et al. Power control in Ad hoc networks: theory architecture algorithm and implementation of the COMPOW protocol[C]//Proc of European Wireless Conference. 2002:156-162.
[15]BLOUGH D M LEONCINI M RESTA G，et al. The K-neigh protocol for symmetric topology control in Ad hoc networks[C]//Proc of the 4th ACM International Symposium on Mobile Ad hoc Networking and Computing. New York: ACM Press 2003.
[16]GUBA S KHULLER S. Approximation algorithms for connected dominating sets[J].Algorithmica，1998，20(4):374-387.
[17]DAS B BHARGHAVAN V. Routing in Ad hoc networks using minimum connected dominating set[C]//Proc of International Conference on Communication(ICC). 1997:376-380.
[18]DEB B BHATNAGAR S NATH B. A topology discovery algorithm for sensor networks with applications to network management DCS-TR-441[R].Comden NJ:Rutgers University 2001.
[19]HEINZELMAN W R CHANDRASAN A BALAKRISHNAN H. An application-specific protocol architecture for wireless micro-sensor networks[J]. IEEE Trans on Wireless Communications 2002，1(4):660-670.
[20]XU Ya HEIDEMANN J ESTRIN D. Geography-informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual International Conference on Mobile Computing and Networking. New York: ACM Press 2001:70-84.
[21]SANTI P SIMON J. Silence is golden with probability:maintaining a connected backbone in wireless sensor networks[C]//Proc ofthe 1st European Workshop on Wireless Sensor Networks. Berlin:Springer，2004:106-121.
[22]YOUNIS O FAHMY S. HEED: a hybrid energy-efficient distributed clustering approach for Ad hoc sensor networks[J].IEEE Trans on Mobile Computing，2004，3(4):660-669.
[23]KWON T J GERLA M. Clustering with power control[C]//Proc of the 4th IEEE Military Communications Conference. Atlantic City:IEEE Press，1999:1424-1428.
[24]CHIASSERINIC F CHLAMTAC I MONTI P et al.Energy efficient design of wireless Ad hoc networks[C]//Proc of the 2nd IFIP Networking Conference. London: Spring-Verlag 2002:376-386.
[25]KAWADIA V KUMAR P R. Power control and clustering in Ad hoc networks[C]//Proc of the 22nd Ammual Joint Conference on IEEE Computer and Communications Societies. New York: IEEE Press，2003:459-469.
[26]SCHURGERS C TSIATSIS V GANERIWAL S et al. Topology management for sensor networks: exploiting latency and density[C]//Proc of the 3rd ACM International Symposium on Mobile Ad hoc Networking Colllputing. New York: ACM Press 2002:135-145.
[27]CERPA A ESTRIN D. ASCENT: adaptive self-configuring sensor networks topologies[J].IEEE Trans on Mobile Computing 2004，3:272-285.
[28]TIAN Di GEORGANAS N D. A coverage-preserving node scheduling scheme for large wireless sensor networks[C]//Proc of the 1st ACM Workshop on Wireless Sensor Networks and Applications. New York: ACM Press 2002:32-41.
[29]SANTI P. Topology control in wireless Ad hoc and sensor networks[J].ACM Computing Surveys 2005，37(2):164-194.
[30]KAWADIA V KUMAR P R. A cautionary perspective on cross-layer design[J].IEEE Wireless Communications，2005，12(1):3-11.
