基于Bloom filter的遠程對稱差規模估算法

摘 要：在內容分發網絡、閑談協議、移動數據同步等分布式系統中，遠程主機上集合對稱差規模的估算準確程度，直接影響基于CPISync算法的集合調和方法的消息交換輪數以及調和時間。對稱差規模的估算誤差越低，則集合調和的速度越快。本文提出了基于布魯姆過濾器的準交集查詢法，該算法可顯著降低對稱差規模的估算誤差，提高調和算法的效率。

關鍵詞：移動計算；布魯姆過濾器；集合調和；數據同步

中圖分類號：TP393 文獻標識碼：A

1 引言

隨著網絡基礎設施的日趨完善和無線通信技術的發展，移動計算設備的計算和待機能力也在逐步提高，人們對使用PDA、智能手機、平板電腦等移動設備進行移動計算的要求越來越普及，加上對等網絡（peer-to-peer， P2P）技術的研究和應用日益深入，出現了移動P2P計算（mobile peer-to-peer computing）[1-5]的研究熱點。

移動P2P計算領域中通常有兩類數據同步方案：慢同步和快同步。慢同步時在同步終端之間傳輸所有數據，由于同步終端間的實際差異往往遠小于實際數據集規模，因此該方法在帶寬占用和時延方面效率較低。目前研究人員較關注的是快同步方案，即同步終端間僅傳輸相異數據，以達到改善帶寬效率和時延效率的目的，如文獻[6]提出了兩種基于特征多項式插值同步算法（characteristic polynomial interpolation -based synchronization， CPISync）的快同步技術方案：確定性方案和概率性方案。確定性方案是在已知遠程集合的對稱差規模時使用的，但是，在移動計算領域，由于遠程集合的對稱差規模無法事先了解，只能使用概率性方案。文獻[6]中的概率性方案不能在單輪數據交換過程中完成數據同步，必須試探性地逐輪增加插值點個數（稱試探法），這樣就可能造成多輪數據交換導致數據同步的時延過長。另外，文獻[7]提出了一種分而治之的劃分法，以降低算法的計算復雜度。其具體做法如下：將整個全集空間遞歸地劃分為若干個子分區，直至子分區足夠小，僅需調用一次CPISync算法可完成子分區的調和為止。設d為對稱差規模，劃分法同步只需（d）計算復雜度，但以節點之間更多的數據交換輪數為代價[7]。因此，如果能用布魯姆過濾器（Bloom filter， BF）結構估算出對稱差規模的較準確值，然后再調用CPISync算法，就能用較少的數據交換輪數（最好情況是1輪）完成數據同步，提高這類概率性方案的同步時延效率。

本文第2節介紹現有的基于Bloom filter的遠程對稱差規模估算方法，并提出了準交集查詢法。第3節是各估算方法的實驗比較部分。第4節將各對稱差規模估算方法用于P2P系統中的集合調和，測試算法在實際系統中的應用性能。第5節是本文工作的總結。

2 基于Bloom filter的對稱差規模估算方法

2.1 計數布魯姆過濾器法

由圖4可看出，使用準交集查詢法的集合調和過程其一次插值成功率總體來說優于其它方法，性能優勢較為突出。

事實上，如果我們對算法2稍作修改：使用布魯姆過濾器估算出對稱差規模值d0后，在算法2的第2步，多計算10%（0.1d0）的特征多項式值，節點A首次即使用（1.1d0+r +1）個特征多項式值進行插值，然后確認、因式分解等，則算法能顯著地提高一次插值成功率（圖5），降低數據交換輪數，從而減少調和時間。這樣做僅需增加少量的數據傳輸位數，但能顯著減少數據交換輪數，這在分布式系統中是完全可行的。

由圖5可看出，對算法2按如上所述進行修改后，除內積法外，其他方法均能使集合調和的一次插值成功率達到100%或極為接近100%，以計數布魯姆過濾器法的性能最為突出，其一次插值成功率始終為100%，而準交集查詢法和布魯姆過濾器交互查詢法在對稱差規模較小時稍差，為98%-99%。內積法、準交集查詢法和布魯姆過濾器交互查詢法如果其一次插值成功率為100%，即僅需1次插值算法的調用，則意味著使用這些估算方法的特征多項式插值調和過程只需要1輪數據交換即可完成。但布魯姆過濾器交互查詢法由于在估算對稱差規模時需要使用1輪數據交換才能完成，因此，即使其只需調用1次插值算法，它也需2輪數據交換才能完成調和。

5 結論

由于準交集查詢法估算能得到對稱差規模的較準確值，從而使用準交集查詢法的集合調和過程總體來說比使用其它方法的集合調和過程要好得較多，插值次數、調和時間和一次插值成功率均有較突出的優勢，綜合起來其性能表現是最好的，是一種值得推薦的好方法。而內積法由于其對稱差規模估算準確程度最低，從而數據調和性能也是最差的，在分布式系統中應該盡量避免使用這種方法。而計數布魯姆過濾器法則由于其較準確的估算程度，從而能得到較好的調和時間、插值次數及一次插值成功率，尤其是在對算法2作了修改后，其一次插值成功率在仿真實驗過程中始終為100%，是一種可以推薦使用的實用方法。而使用布魯姆過濾器交互查詢法的集合調和過程則由于其數據交換總輪數不少于2輪，其調和時間較長，我們不推薦使用。

參考文獻

[1]F S Tsai， W Han， J Xu， et al. Design and development of a mobile peer-to-peer social networking application [J]. Expert systems with applications， 2009， 36（8）： 11077-11087.

[2]C Y Chow， M F Mokbel， X Liu. Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments [J]. GeoInformatica， 2011， 15（2）： 351-380.

[3]T Delot， N Cenerario， S Ilarri. Vehicular event sharing with a mobile peer-to-peer architecture [J]. Transportation Research Part C： Emerging Technologies， 2010， 18（4）： 584-598.

[4]ó R Helgason， E A Yavuz， S T Kouyoumdjieva， et al. A mobile peer-to-peer system for opportunistic content-centric networking [C]// Proceedings of the second ACM SIGCOMM workshop on Networking systems， and applications on mobile handhelds， 2010： 21-26.

[5]W S Yang， S Y Hwang， Y W Shih. Facilitating information sharing and social interaction in mobile peer-to-peer environment [C]// Proceedings of the 2012 IEEE International Conference on Pervasive Computing and Communications Workshops （PERCOM Workshops）， Lugano， 2012： 673-678.

[6]D Starobinski， A Trachtenberg， S Agarwal. Efficient PDA synchronization [J]. IEEE Transactions on Mobile Computing， 2003， 2（1）： 40-51.

[7]Y Minsky， A Trachtenberg. Practical set reconciliation [R]. Boston ： Boston University， 2002.

[8]S Agarwal， A Trachtenberg. Approximating the number of differences between remote sets [C]//Proceedings of the Information Theory Workshop， Chengdu， 2006： 217-221.

[9]A Broder， M Mitzenmacher. Network applications of bloom filters： A survey [J]. Internet Mathematics， 2005， 1（4）： 485-509.

[10]H Chen， H Jin， J Wang， et al. Efficient multi-keyword search over p2p web [C]//Proceedings of the the 17th International Conference on World Wide Web， New York， 2008： 989-998.

[11]I Stoica， R Morris， D Karger， et al. Chord： A scalable peer-to-peer lookup service for internet applications [J]. ACM SIGCOMM Computer Communication Review， 2001， 31（4）： 149-160.

[12]E W Zegura， K L Calvert， S Bhattacharjee. How to model an internetwork [C]//Proceedings of the INFOCOM 1996， San Francisco， 1996： 594-602.