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