TOPDISC算法是基于最小支配理論的經(jīng)典算法，它首先由初始節(jié)點(diǎn)發(fā)出拓?fù)浒l(fā)現(xiàn)請(qǐng)求，通過(guò)廣播該消息來(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)，光電開(kāi)關(guān)的TOPDISC算法采用的是貪婪算法。具體地，TOPDISC提出了兩種類似的方法：三色法和四色法。
在三色算法中，節(jié)點(diǎn)可以處于三種不同狀態(tài)，分別用白色、黑色、灰色三種顏色表示：
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)關(guān)傳感器的所有節(jié)點(diǎn)都被標(biāo)記為白色，算法由一個(gè)初始節(jié)點(diǎn)發(fā)起，算法結(jié)束后所有節(jié)點(diǎn)都將被標(biāo)記為黑色或者灰色(前提假設(shè)整個(gè)網(wǎng)絡(luò)拓?fù)涫沁B通的)。光電開(kāi)關(guān)的TOPDISC采用兩種啟發(fā)方法來(lái)使得每個(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)的節(jié)瞇之間的距離。三色法的詳細(xì)過(guò)程描述如下：
1、初始節(jié)點(diǎn)被標(biāo)注記為黑色，并向網(wǎng)絡(luò)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求;
2、當(dāng)白色節(jié)瞇收到來(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í)間TWC后標(biāo)記為黑色，但如果在等待周期又收到來(lái)自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求則先優(yōu)先標(biāo)記為灰色;同樣，等待時(shí)間TWG反比于該白色節(jié)點(diǎn)與灰色節(jié)點(diǎn)之間的距離。不管節(jié)點(diǎn)被標(biāo)記為灰色還是黑色，都將在完成顏色標(biāo)記后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請(qǐng)求;
4、所有已被標(biāo)記為黑色或者灰色的節(jié)點(diǎn)，都將忽略其他節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請(qǐng)求。
為了使得每個(gè)新的黑色節(jié)點(diǎn)都盡可能多地覆蓋還沒(méi)有被覆蓋的節(jié)點(diǎn)，光電開(kāi)關(guān)傳感器的TOPDISC采用了反比于節(jié)點(diǎn)之間距離的轉(zhuǎn)發(fā)延時(shí)機(jī)制。其合理懷簡(jiǎn)單解釋為：理想情況下，節(jié)點(diǎn)的覆蓋面積和局部的節(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)覆蓋的面積之差。 |
當(dāng)前位置：
