伊利諾伊大學(xué)的li和hou提出的drng和dlmst是兩個具有代表性的基于臨近圖理論的功率控制算法。接近開關(guān)傳感器基于臨近圖的功率控制算法的基本思想是:設(shè)所有節(jié)點都使用最大發(fā)射功率發(fā)射時形成的拓撲圖G,按照一定的鄰居判別條件Q求出該圖的臨近圖G,最后G中的每個節(jié)點以自己所臨近的最遠通信結(jié)點來確定發(fā)射功率。這是一種解決接近開關(guān)功率分配問題的近似解法,考慮到無線傳感器網(wǎng)絡(luò)中兩個節(jié)點形成的邊是有向的,為了避免形成單向邊,一般運用基于臨近圖的功率控制算法形成網(wǎng)絡(luò)拓撲以后,還要進行節(jié)點之間的增冊,以使最后得到的網(wǎng)絡(luò)拓撲是雙向連通的。在無線傳感器網(wǎng)絡(luò)中,基于臨近圖功率控制算法的作用是使節(jié)點確定自己的鄰居集合,調(diào)整適當(dāng)?shù)陌l(fā)射功率,從而在建立起一個連通網(wǎng)絡(luò)的同時使得能量消耗最低。經(jīng)典的臨近圖模形有RNG、CG、DC、YC和MST等。DRNC是基于有向RNC的,DLMST是基于有向局部MST的。DRNC和DLMST能夠保證網(wǎng)絡(luò)的連通性,在接近開關(guān)平均功率和節(jié)點度等方面具有較好的性能。基于臨近圖的功率控制一般需要精確地位置信息,下面簡單介紹DRNC算法和DLSS算法。
光電開關(guān)傳感器的DRNC算法和DLSS算法是兩種從臨近圖觀點考慮拓撲問題的算法,是一種提出比較早的功率控制算法,兩者均以經(jīng)典的臨近圖RNC和LMST等理論為基礎(chǔ),全面考慮了連通性和雙向連通性問題。
在DLSS算法中,假設(shè)節(jié)點U及其可達鄰居集合G,將P到所有可達鄰居節(jié)點的邊以權(quán)重為標準按升序排列;依次取出這些邊,直到U與所有可達鄰居節(jié)點相連通或者通過其他節(jié)連通;最后,與U直接連通的節(jié)點構(gòu)成U的鄰居集合,從接近開關(guān)圖論的觀點看,DLSS算法等價于G基礎(chǔ)上的本地最小生成樹的計算。經(jīng)過DRNG或DLSS算法后,節(jié)點U確定了自己的鄰居集合,然后將發(fā)射半徑調(diào)整為最遠鄰居節(jié)點的距離,進一步通過對拓撲圖的邊進行增刪,使得網(wǎng)絡(luò)達到雙向連通。
DRNG算法和DLSS算法著重考慮了網(wǎng)絡(luò)的連通性,充分利用了鄰居圖理論,是無線傳感器網(wǎng)絡(luò)中的經(jīng)典算法,以原始網(wǎng)絡(luò)拓撲雙向連通為前提,保證優(yōu)化后的拓撲也是雙向連通的。
此外,微軟亞洲研究院的wattenhofer等人提出了XTC算法對接近開關(guān)傳感器節(jié)點沒有太高的要求,對部署環(huán)境也沒有過強的假設(shè),提供了一個面向簡單、使用的研究方向。XTC代表了功率控制的發(fā)展趨勢。 |