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

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

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

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

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