引言
　　
　　無(wú)線傳感器網(wǎng)絡(luò)（WirelessSensorNetworks，WSN）是由任意散落在被監(jiān)測(cè)區(qū)域內(nèi)大量傳感器節(jié)點(diǎn)以自組織形式構(gòu)成的網(wǎng)絡(luò)，并通過(guò)網(wǎng)絡(luò)將監(jiān)測(cè)數(shù)據(jù)傳送到接收站進(jìn)行處理。通過(guò)隨機(jī)投放的方式，眾多傳感器節(jié)點(diǎn)被密集部署于監(jiān)控區(qū)域。這些傳感器節(jié)點(diǎn)集成有傳感器、數(shù)據(jù)處理單元和通信模塊，它們通過(guò)無(wú)線信道相連，自組織地構(gòu)成網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點(diǎn)間有良好的協(xié)作能力，通過(guò)局部的數(shù)據(jù)交換來(lái)完成全局任務(wù)。通過(guò)網(wǎng)關(guān)、傳感器網(wǎng)絡(luò)還可以連接到現(xiàn)有的網(wǎng)絡(luò)設(shè)施上（如Internet、移動(dòng)通信網(wǎng)絡(luò)等），從而將采集到的信息傳回給遠(yuǎn)程的終端用戶使用。隨著微電子技術(shù)、通信技術(shù)和計(jì)算機(jī)技術(shù)的飛速發(fā)展，WSN在軍事和民用各個(gè)領(lǐng)域都得到廣泛應(yīng)用，其應(yīng)用潛力巨大，已成為目前通信領(lǐng)域的研究熱點(diǎn)。
　　
　　1、無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂?br />　　
　　WSN網(wǎng)絡(luò)拓?fù)淇刂浦饕芯康膯?wèn)題是：在保證網(wǎng)絡(luò)覆蓋度和聯(lián)通性的前提下，設(shè)置或調(diào)整節(jié)點(diǎn)的發(fā)射功率，并按照一定的原則選擇合適的節(jié)點(diǎn)成為骨干節(jié)點(diǎn)，參與網(wǎng)絡(luò)中數(shù)據(jù)的處理和傳輸，達(dá)到優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的目的，其首要的設(shè)計(jì)目標(biāo)是通過(guò)使用能量使網(wǎng)絡(luò)生命期zui大化。
　　
　　WSN中拓?fù)淇刂瓶梢苑譃閮蓚€(gè)研究方向：功率控制和層次拓?fù)浣Y(jié)構(gòu)控制。功率控制機(jī)制調(diào)整網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的發(fā)射功率，保證網(wǎng)絡(luò)連通，在均衡節(jié)點(diǎn)中直接鄰居數(shù)目（單跳可達(dá)鄰居數(shù)目）的同時(shí)，降低節(jié)點(diǎn)之間的通信干擾。層次拓?fù)淇刂剖抢梅执厮枷耄咕W(wǎng)絡(luò)中的部分節(jié)點(diǎn)處于激活狀態(tài)，成為簇頭節(jié)點(diǎn)。由這些簇頭節(jié)點(diǎn)構(gòu)建一個(gè)連通的網(wǎng)絡(luò)來(lái)處理和傳輸網(wǎng)絡(luò)中的數(shù)據(jù)，并定期或不定期地重新選擇簇頭節(jié)點(diǎn)，以均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗。WSN中，節(jié)點(diǎn)的無(wú)線通信模塊處于發(fā)送狀態(tài)下功耗zui高，接收狀態(tài)和空閑狀態(tài)下功耗次之，休眠狀態(tài)下功耗zui低。例如，目前用于WSN的主流傳感器BerkeleyMotes，其通信模塊處于發(fā)送狀態(tài)的功耗為60mW，接收狀態(tài)和空閑狀態(tài)的功耗均為12mW，休眠狀態(tài)的功耗為0.03mW，其功耗比達(dá)到2000：400：1，因此降低能耗的關(guān)鍵是降低網(wǎng)絡(luò)內(nèi)的通信流量，使更多的節(jié)點(diǎn)在更長(zhǎng)時(shí)間段處于休眠狀態(tài)。為了大幅度降低無(wú)線通信模塊的能量消耗，可以考慮依據(jù)一定的機(jī)制選擇部分節(jié)點(diǎn)作為骨干節(jié)點(diǎn)，這些節(jié)點(diǎn)的通信模塊處于打開(kāi)狀態(tài)，而其他非骨干節(jié)點(diǎn)的通信模塊處于關(guān)閉。在這種機(jī)制下，節(jié)點(diǎn)被分為骨干節(jié)點(diǎn)和非骨干節(jié)點(diǎn)兩類，骨干節(jié)點(diǎn)對(duì)非骨干節(jié)點(diǎn)進(jìn)行管轄。這類算法將網(wǎng)絡(luò)分為相連的區(qū)域，稱為分簇算法。
　　
　　在層次拓?fù)淇刂品矫妫呀?jīng)提出的算法有Deb的TopDisc（TopologyDiscory）拓?fù)浒l(fā)現(xiàn)算法、Santi的改進(jìn)GAF（GeographicalAdaptiveFidelity）分簇算法、Heinzelman的LEACH（LOWEnergyAdaptiveChlsteringHierarchy）算法和Younis的HEED算法等。
　　
　　在此，以經(jīng)典的基于zui小支配集理論TopDisc算法為研究對(duì)象。通過(guò)考慮節(jié)點(diǎn)電量的剩余情況，得到Power-balancedTopDisc算法。該算法將節(jié)點(diǎn)剩余能量作為分簇結(jié)構(gòu)的構(gòu)建依據(jù)，對(duì)剩余能量較少的節(jié)點(diǎn)賦予一定的約束，使之成為普通節(jié)點(diǎn)，從而均衡網(wǎng)絡(luò)電量負(fù)載，解決網(wǎng)絡(luò)中部分低電量節(jié)點(diǎn)擔(dān)任骨干節(jié)點(diǎn)而導(dǎo)致的能耗問(wèn)題，有效延長(zhǎng)網(wǎng)絡(luò)生命期。仿真實(shí)驗(yàn)結(jié)果證明了該算法的有效性。
　　
　　2、TopDisc算法
　　
　　在TopDisc算法中，首先由初始節(jié)點(diǎn)發(fā)出拓?fù)浒l(fā)現(xiàn)請(qǐng)求，通過(guò)廣播該請(qǐng)求消息來(lái)確定網(wǎng)絡(luò)中的骨干節(jié)點(diǎn)，并結(jié)合這些骨干節(jié)點(diǎn)中鄰居節(jié)點(diǎn)的信息形成網(wǎng)絡(luò)拓?fù)涞慕仆負(fù)洹Ｔ谶@個(gè)近似拓?fù)湫纬梢院螅瑸榱藴p小算法本身引起的網(wǎng)絡(luò)通信量，只有骨干節(jié)點(diǎn)才對(duì)初始節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求作出相應(yīng)的響應(yīng)。
　　
　　為了確定網(wǎng)絡(luò)中的骨干節(jié)點(diǎn)，TopDisc算法采用的是貪婪算法。具體分為兩種類型：三色法和四色法。
　　
　　2.1三色法
　　
　　在三色算法中，節(jié)點(diǎn)可以處于三種不同狀態(tài)。在TopDisc算法中，分別用白色、黑色、灰色三種顏色表示：
　　
　　（1）白色是尚未被發(fā)現(xiàn)的節(jié)點(diǎn)，或者說(shuō)是沒(méi)有接收到任何拓?fù)浒l(fā)現(xiàn)請(qǐng)求的節(jié)點(diǎn)；
　　
　　（2）黑色是骨干節(jié)點(diǎn)（簇頭節(jié)點(diǎn)），負(fù)責(zé)響應(yīng)拓?fù)浒l(fā)現(xiàn)請(qǐng)求；
　　
　　（3）灰色是普通節(jié)點(diǎn)，至少被一個(gè)標(biāo)記為黑色的節(jié)點(diǎn)覆蓋，即黑色節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。
　　
　　在開(kāi)始階段，所有節(jié)點(diǎn)都被標(biāo)記為白色，算法由一個(gè)初始節(jié)點(diǎn)發(fā)起，算法結(jié)束后所有節(jié)點(diǎn)都將被標(biāo)記為黑色或者灰色（假設(shè)整個(gè)網(wǎng)絡(luò)拓?fù)涫沁B通的）。Top-Disc使用兩種啟發(fā)式方法，使得每個(gè)新的黑色節(jié)點(diǎn)都盡可能多地覆蓋還沒(méi)有被覆蓋到的節(jié)點(diǎn)：一種是節(jié)點(diǎn)顏色標(biāo)記方法；另一種是節(jié)點(diǎn)轉(zhuǎn)發(fā)拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)會(huì)故意延時(shí)一段時(shí)間，延時(shí)時(shí)間的長(zhǎng)度反比于該節(jié)點(diǎn)與發(fā)送拓?fù)浒l(fā)現(xiàn)請(qǐng)求到該節(jié)點(diǎn)之間的距離。具體算法過(guò)程如下：
　　
　　（1）初始節(jié)點(diǎn)被標(biāo)記為黑色，并向網(wǎng)絡(luò)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求；
　　
　　（2）當(dāng)白色節(jié)點(diǎn)收到來(lái)自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，將被標(biāo)記為灰色，并在延時(shí)時(shí)間tWB后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求。tWB反比于它與黑色節(jié)點(diǎn)之間的距離。
　　
　　（3）當(dāng)白色節(jié)點(diǎn)收到來(lái)自灰色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，將在等待時(shí)間tWG后標(biāo)記為黑色，但如果在等待期間，又收到來(lái)自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，則優(yōu)先標(biāo)記為灰色；同樣，等待時(shí)間反比于該白色節(jié)點(diǎn)與灰色節(jié)點(diǎn)之間的距離。不管節(jié)點(diǎn)被標(biāo)記為灰色還是黑色，都將在完成顏色標(biāo)記之后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求；
　　
　　（4）所有已經(jīng)被標(biāo)記為黑色或者灰色的節(jié)點(diǎn)，都將忽略其他節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求。
　　
　　為了使每個(gè)新的黑色節(jié)點(diǎn)都盡可能多地覆蓋還沒(méi)有被覆蓋的節(jié)點(diǎn)，TopDisc采用反比于節(jié)點(diǎn)之間距離的轉(zhuǎn)發(fā)延時(shí)機(jī)制。理想情況下，節(jié)點(diǎn)的覆蓋范圍是半徑為無(wú)線電發(fā)射半徑的圓。于是，單個(gè)節(jié)點(diǎn)所能夠覆蓋的節(jié)點(diǎn)數(shù)目正比于其覆蓋面積和局部節(jié)點(diǎn)部署密度。對(duì)于一個(gè)正在轉(zhuǎn)發(fā)拓?fù)浒l(fā)現(xiàn)請(qǐng)求的節(jié)點(diǎn)，它所能夠覆蓋的新節(jié)點(diǎn)（還沒(méi)有被任何節(jié)點(diǎn)覆蓋）則正比于它的覆蓋面積與已經(jīng)覆蓋的面積之差。
　　
　　2.2四色法
　　
　　為了增大簇之間的間隔，減少重疊區(qū)域，TopDisc算法還提出了四色法。節(jié)點(diǎn)可以處于四種不同的狀態(tài)，分別用白色、黑色、灰色和深灰色表示。前三種顏色代表的含義與三色法相同，增加的深灰色表示節(jié)點(diǎn)收到過(guò)拓?fù)浒l(fā)現(xiàn)請(qǐng)求，但不被任何標(biāo)記為黑色的節(jié)點(diǎn)覆蓋。
　　
　　在初始階段，所有節(jié)點(diǎn)被標(biāo)記為白色，算法由一個(gè)初始節(jié)點(diǎn)發(fā)起，算法結(jié)束后所有節(jié)點(diǎn)都將被標(biāo)記為黑色或灰色（假設(shè)整個(gè)網(wǎng)絡(luò)拓?fù)涫沁B通的，注意zui終沒(méi)有標(biāo)記為深灰色的節(jié)點(diǎn)）。詳細(xì)過(guò)程描述如下：
　　
　　（1）初始節(jié)點(diǎn)被標(biāo)記為黑色，并向網(wǎng)絡(luò)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求；
　　
　　（2）當(dāng)白色節(jié)點(diǎn)收到來(lái)自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，將標(biāo)記為灰色，并在延時(shí)時(shí)間tWB后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求。tWB反比于它與黑色節(jié)點(diǎn)之間的距離；
　　
　　（3）當(dāng)白色節(jié)點(diǎn)收到來(lái)自灰色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，將標(biāo)記為深灰色并繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求，然后等待一段時(shí)間tWG（同樣與距離成反比）。如果在等待期間收到來(lái)自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，則改變?yōu)榛疑駝t它自己成為黑色；
　　
　　（4）當(dāng)白色節(jié)點(diǎn)收到來(lái)自深灰色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，等待一段時(shí)間（同樣與距離成反比）。如果在等待期間，收到來(lái)自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求時(shí)，則改變?yōu)榛疑駝t它自己變?yōu)楹谏V播拓?fù)浒l(fā)現(xiàn)請(qǐng)求；
　　
　　（5）所有已經(jīng)被標(biāo)記為黑色或者灰色的節(jié)點(diǎn)，都將忽略其他節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求。
　　
　　與三色法相比，四色法形成的簇?cái)?shù)目更少，簇與簇之間的重疊區(qū)域也更小。但是可能形成一些孤立的標(biāo)記為黑色的節(jié)點(diǎn)不覆蓋任何灰色節(jié)點(diǎn)。雖然三色法和四色法形成的黑色節(jié)點(diǎn)數(shù)目相當(dāng)，但四色法中傳輸?shù)臄?shù)據(jù)量要少一些。
　　
　　TopDisc算法利用圖論中的經(jīng)典算法，提出了一種有效方法來(lái)構(gòu)建網(wǎng)絡(luò)的近似拓?fù)洌欠执厮惴ㄖ械慕?jīng)典算法。它是一種只需要利用局部信息，且*分布時(shí)可擴(kuò)展的網(wǎng)絡(luò)拓?fù)淇刂扑惴ā５泊嬖谛枰倪M(jìn)的地方，如算法開(kāi)銷偏大；沒(méi)有考慮節(jié)點(diǎn)剩余電量的信息。
　　
　　3、Power-balancedTopDisc算法
　　
　　WSN中節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的耗能模型如下所述。
　　
　　傳感器節(jié)點(diǎn)發(fā)射r比特?cái)?shù)據(jù)包所消耗的能量為：
　　
　　Pt（r，d）=r（a1+a2dn）（1）
　　
　　式中：d為兩節(jié)點(diǎn)之間的距離；a1是與距離無(wú)關(guān)的量，包括發(fā)射電路所耗能量等；a2是與距離有關(guān)的量；n為路徑損耗指數(shù)，通常取2～4之間。
　　
　　傳感器節(jié)點(diǎn)接收r比特?cái)?shù)據(jù)包所消耗的能量為：
　　
　　Pr（r）=rβ（2）
　　
　　式中：β盧為接收能量系數(shù)。
　　
　　傳感器節(jié)點(diǎn)將2個(gè)數(shù)據(jù)流r1和r2融合成一個(gè)數(shù)據(jù)包r的耗能為：
　　
　　Pa（r1+r2，r）=r（r1+r2-r）（3）
　　
　　式中：r為數(shù)據(jù)融合系數(shù)。
　　
　　從式（1）～式（3）可以看出，若剩余能量較少的節(jié)點(diǎn)仍然承擔(dān)著較重的轉(zhuǎn)發(fā)任務(wù)，那么就很可能導(dǎo)致該節(jié)點(diǎn)過(guò)早死亡，從而影響網(wǎng)絡(luò)生命時(shí)間的延續(xù)。所以，在構(gòu)建無(wú)線傳感器網(wǎng)絡(luò)拓?fù)鋾r(shí)，節(jié)點(diǎn)應(yīng)選擇剩余能量多的節(jié)點(diǎn)作為數(shù)據(jù)轉(zhuǎn)發(fā)的主要節(jié)點(diǎn)，而剩余能量較少的節(jié)點(diǎn)作為數(shù)據(jù)源節(jié)點(diǎn)，這樣將有效解決由于負(fù)載過(guò)大而過(guò)早死亡的問(wèn)題。
　　
　　為便于描述和分析，作如下假設(shè)：
　　
　　（1）每個(gè)節(jié)點(diǎn)都具有相同的zui大發(fā)射功率，其覆蓋范圍是半徑為R的圓形區(qū)域，且可通過(guò)調(diào)節(jié)發(fā)射功率以適應(yīng)其覆蓋范圍內(nèi)不同距離節(jié)點(diǎn)的通信；
　　
　　（2）每個(gè)節(jié)點(diǎn)都能夠獲得自身的剩余能量，有一定的存儲(chǔ)空間來(lái)存放鄰居節(jié)點(diǎn)信息；
　　
　　（3）忽略真實(shí)環(huán)境中存在障礙物等影響通信質(zhì)量的因素，確保所有的數(shù)據(jù)包都能夠可靠傳輸。
　　
　　考慮節(jié)點(diǎn)電量均衡因素，在TopDisc四色法的步驟（3）中，對(duì)tWG進(jìn)行修正，公式為：
　　
　　twG=a1／d+a2／p（4）
　　
　　式中：d為節(jié)點(diǎn)之間的距離；p為當(dāng)前節(jié)點(diǎn)剩余的電量；a1和a2為預(yù)設(shè)參數(shù)。對(duì)tWG進(jìn)行修正后得到Power-balancedTopDise算法。
　　
　　Power-balancedTopDise算法的合理性可以由圖1說(shuō)明。圖1（a）為T(mén)opDisc算法的分簇結(jié)果；圖1（b）為Power-balancedTopDise算法的分簇結(jié)果。其中，電量為80的節(jié)點(diǎn)為初始節(jié)點(diǎn)。初始節(jié)點(diǎn)發(fā)出拓?fù)浒l(fā)現(xiàn)請(qǐng)求到電量為20的節(jié)點(diǎn)變?yōu)榛疑⒗^續(xù)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求。電量為30和90的節(jié)點(diǎn)同時(shí)收到拓?fù)浒l(fā)現(xiàn)請(qǐng)求。在Power-balancedTopDisc算法中，電量為90的節(jié)點(diǎn)先于電量為30的節(jié)點(diǎn)變?yōu)楹谏闯蔀楣歉晒?jié)點(diǎn)（簇頭節(jié)點(diǎn)）。
　　
　　經(jīng)過(guò)上述基于電量均衡的Power-balancedTopDisc算法處理后，剩余能量較少的節(jié)點(diǎn)將不再擔(dān)當(dāng)骨干節(jié)點(diǎn)，有利于延長(zhǎng)網(wǎng)絡(luò)的生命周期，從而實(shí)現(xiàn)均衡耗能。
　　
　　4、性能分析和實(shí)驗(yàn)
　　
　　為評(píng)估Power-balancedTopDise算法的性能，采用軟件進(jìn)行多次仿真試驗(yàn)，以所獲得的分簇結(jié)構(gòu)作為主要性能指標(biāo)，并與TopDisc算法進(jìn)行比較。
　　
　　仿真模擬配置如下：假設(shè)有400個(gè)節(jié)點(diǎn)隨機(jī)地部署在一個(gè)400×400的正方形平面區(qū)域內(nèi)；每個(gè)節(jié)點(diǎn)的剩余能量為1～100的隨機(jī)值。由TopDisc算法和Power-balancedTopDisc算法所生成的分簇結(jié)構(gòu)分別如圖2和圖3所示。
　　
　　對(duì)于該WSN，TopDisc算法得到的分簇結(jié)果是骨干節(jié)點(diǎn)平均電量為51；Power-balancedTopDisc算法得到的分簇結(jié)果是骨干節(jié)點(diǎn)平均電量為56。由于Power-balancedTopDisc算法生成的分簇結(jié)構(gòu)考慮了節(jié)點(diǎn)的剩余電量，因而它使得剩余能量較少的節(jié)點(diǎn)成為普通節(jié)點(diǎn)，節(jié)省了擔(dān)當(dāng)骨干節(jié)點(diǎn)耗費(fèi)的能量，從而延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命周期。
　　
　　5、結(jié)語(yǔ)
　　
　　在此，提出一種基于電量均衡的Power-balancedTopDisc算法，該算法考慮了節(jié)點(diǎn)中剩余電量的多少，對(duì)節(jié)點(diǎn)賦予一定的約束，讓剩余能量較多的節(jié)點(diǎn)擔(dān)當(dāng)骨干節(jié)點(diǎn)，承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，保證了低電量節(jié)點(diǎn)不會(huì)因轉(zhuǎn)發(fā)過(guò)多數(shù)據(jù)而過(guò)早失效，從而延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命期，實(shí)驗(yàn)結(jié)果證明了該算法的有效性。