(2)當(dāng)白色節(jié)點(diǎn)收到來自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí)，將被標(biāo)記為灰色，并在延時(shí)時(shí)間tWB后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請求。tWB反比于它與黑色節(jié)點(diǎn)之間的距離。

(3)當(dāng)白色節(jié)點(diǎn)收到來自灰色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí)，將在等待時(shí)間tWG后標(biāo)記為黑色，但如果在等待期間，又收到來自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(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)請求；

(4)所有已經(jīng)被標(biāo)記為黑色或者灰色的節(jié)點(diǎn)，都將忽略其他節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求。

為了使每個(gè)新的黑色節(jié)點(diǎn)都盡可能多地覆蓋還沒有被覆蓋的節(jié)點(diǎn)，TopDisc采用反比于節(jié)點(diǎn)之間距離的轉(zhuǎn)發(fā)延時(shí)機(jī)制。理想情況下，節(jié)點(diǎn)的覆蓋范圍是半徑為無線電發(fā)射半徑的圓。于是，單個(gè)節(jié)點(diǎn)所能夠覆蓋的節(jié)點(diǎn)數(shù)目正比于其覆蓋面積和局部節(jié)點(diǎn)部署密度。對于一個(gè)正在轉(zhuǎn)發(fā)拓?fù)浒l(fā)現(xiàn)請求的節(jié)點(diǎn)，它所能夠覆蓋的新節(jié)點(diǎn)(還沒有被任何節(jié)點(diǎn)覆蓋)則正比于它的覆蓋面積與已經(jīng)覆蓋的面積之差。

2.2 四色法

為了增大簇之間的間隔，減少重疊區(qū)域，TopDisc算法還提出了四色法。節(jié)點(diǎn)可以處于四種不同的狀態(tài)，分別用白色、黑色、灰色和深灰色表示。前三種顏色代表的含義與三色法相同，增加的深灰色表示節(jié)點(diǎn)收到過拓?fù)浒l(fā)現(xiàn)請求，但不被任何標(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通的，注意最終沒有標(biāo)記為深灰色的節(jié)點(diǎn))。詳細(xì)過程描述如下：

(1)初始節(jié)點(diǎn)被標(biāo)記為黑色，并向網(wǎng)絡(luò)廣播拓?fù)浒l(fā)現(xiàn)請求；

(2)當(dāng)白色節(jié)點(diǎn)收到來自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí)，將標(biāo)記為灰色，并在延時(shí)時(shí)間tWB后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請求。tWB反比于它與黑色節(jié)點(diǎn)之間的距離；

(3)當(dāng)白色節(jié)點(diǎn)收到來自灰色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí)，將標(biāo)記為深灰色并繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請求，然后等待一段時(shí)間tWG(同樣與距離成反比)。如果在等待期間收到來自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí)，則改變?yōu)榛疑?，否則它自己成為黑色；

(4)當(dāng)白色節(jié)點(diǎn)收到來自深灰色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí)，等待一段時(shí)間(同樣與距離成反比)。如果在等待期間，收到來自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí)，則改變?yōu)榛疑?，否則它自己變?yōu)楹谏V播拓?fù)浒l(fā)現(xiàn)請求；

(5)所有已經(jīng)被標(biāo)記為黑色或者灰色的節(jié)點(diǎn)，都將忽略其他節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求。

與三色法相比，四色法形成的簇?cái)?shù)目更少，簇與簇之間的重疊區(qū)域也更小。但是可能形成一些孤立的標(biāo)記為黑色的節(jié)點(diǎn)不覆蓋任何灰色節(jié)點(diǎn)。雖然三色法和四色法形成的黑色節(jié)點(diǎn)數(shù)目相當(dāng)，但四色法中傳輸?shù)臄?shù)據(jù)量要少一些。

TopDisc算法利用圖論中的經(jīng)典算法，提出了一種有效方法來構(gòu)建網(wǎng)絡(luò)的近似拓?fù)?，是分簇算法中的?jīng)典算法。它是一種只需要利用局部信息，且完全分布時(shí)可擴(kuò)展的網(wǎng)絡(luò)拓?fù)淇刂扑惴ā５泊嬖谛枰倪M(jìn)的地方，如算法開銷偏大；沒有考慮節(jié)點(diǎn)剩余電量的信息。

3 Power-balanced TopDisc算法

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是與距離無關(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)過早死亡，從而影響網(wǎng)絡(luò)生命時(shí)間的延續(xù)。所以，在構(gòu)建無線傳感器網(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ù)載過大而過早死亡的問題。

為便于描述和分析，作如下假設(shè)：

(1)每個(gè)節(jié)點(diǎn)都具有相同的最大發(fā)射功率，其覆蓋范圍是半徑為R的圓形區(qū)域，且可通過調(diào)節(jié)發(fā)射功率以適應(yīng)其覆蓋范圍內(nèi)不同距離節(jié)點(diǎn)的通信；

(2)每個(gè)節(jié)點(diǎn)都能夠獲得自身的剩余能量，有一定的存儲空間來存放鄰居節(jié)點(diǎn)信息；

(3)忽略真實(shí)環(huán)境中存在障礙物等影響通信質(zhì)量的因素，確保所有的數(shù)據(jù)包都能夠可靠傳輸。

考慮節(jié)點(diǎn)電量均衡因素，在TopDisc四色法的步驟(3)中，對tWG進(jìn)行修正，公式為：

twG=a1／d+a2／p    (4)

式中：d為節(jié)點(diǎn)之間的距離；p為當(dāng)前節(jié)點(diǎn)剩余的電量；a1和a2為預(yù)設(shè)參數(shù)。對tWG進(jìn)行修正后得到Power-balanced TopDise算法。