基于Gossip算法的分布式平均共識問題研究.pdf

1、在無線傳感器網(wǎng)絡(luò)中,平均共識問題是一類十分重要的問題。平均共識問題的目標是使得網(wǎng)絡(luò)中所有節(jié)點達到初始狀態(tài)均值的一致狀態(tài),它可以被廣泛的用于參數(shù)估計、定位、同步等方面。對于平均共識問題,如果按照傳統(tǒng)的方法將網(wǎng)絡(luò)中的數(shù)據(jù)直接匯聚到某個節(jié)點中,將造成大量的路由開銷和瓶頸效應(yīng)。而Gossip算法利用節(jié)點的本地信息處理能力,僅通過隨機的喚醒網(wǎng)絡(luò)中的節(jié)點并與鄰居節(jié)點進行數(shù)據(jù)交換的方式使網(wǎng)絡(luò)達到平均共識狀態(tài),從而避免了網(wǎng)絡(luò)中路由的開銷和瓶頸效應(yīng)。由于

2、Gossip算法在分布式信息處理方面的優(yōu)良性質(zhì),受到了學(xué)術(shù)界的廣泛關(guān)注。
　　本文首先建立了平均共識問題和網(wǎng)絡(luò)拓撲結(jié)構(gòu)的一般模型,然后在該模型下對幾種典型的Gossip算法的收斂性和收斂速度進行了分析。單播Gossip算法能夠收斂于網(wǎng)絡(luò)的初始均值,但是收斂速度較慢;而廣播Gossip算法雖然收斂速度較快,但是現(xiàn)有的廣播Gossip算法無法收斂于初始狀態(tài)的均值或者根本就無法證明其收斂性。為了彌補廣播Gossip算法的不足,本文提出了

3、一種基于偵聽的廣播Gossip算法,它既繼承了廣播Gossip算法中利用無線信道天然廣播特性的主要思想,又采用了單播Gossip算法中隨機選擇鄰居節(jié)點的更新模式。接著,利用遍歷系數(shù)的方法證明了基于偵聽的廣播Gossip算法的收斂性。雖然由于算法喚醒概率與具體網(wǎng)絡(luò)結(jié)構(gòu)有關(guān),并沒有得到基于偵聽的廣播Gossip算法收斂速度的數(shù)學(xué)表達式,但是通過仿真比較了該算法與幾種現(xiàn)有廣播Gossip算法的性能。仿真結(jié)果表明,在幾何隨機圖中,基于偵聽的廣播

4、Gossip算法能夠收斂于網(wǎng)絡(luò)的初始均值,并且具有最快的歸一化均方誤差曲線下降速度。隨著網(wǎng)絡(luò)中節(jié)點數(shù)的增加,基于偵聽的廣播Gossip算法的收斂速度有所降低,但是與其他算法相比仍然具有優(yōu)勢,考慮到網(wǎng)絡(luò)中的節(jié)點數(shù)目以及網(wǎng)絡(luò)拓撲結(jié)構(gòu)的未知性,算法的整體性能也值得肯定。在存在鏈路丟失的情況下,算法的收斂性依然能夠得到保障,并且從仿真結(jié)果來看算法的收斂速度也并未受到較大影響。最后介紹了在ARM11平臺上對基于偵聽的廣播Gossip算法的實現(xiàn)方法