是否可以在P2P網絡中進行空間搜索？

我想建立一個基於Javascript/HTML5地理定位的社交網絡，我想知道可能的架構的最佳選擇。客戶端 - 服務器可以很容易開發，但缺點是系統資源可能非常高，尤其是因爲應用程序必須管理移動（最壞的情況：汽車中的用戶必須看到汽車周圍的其他用戶）。是否可以在P2P網絡中進行空間搜索？

Basicaly，在客戶端 - 服務器架構，服務器任務將是：

收集並存儲緯度和用戶的經度（可能有幾千條）
使地理距離搜索該用戶（獲取用戶在他周圍的用戶列表）
建立並向客戶端發送用戶在列表中的位置的XML文件

這3個操作必須定期進行，每3或5秒進行一次，因爲我需要一張「活」地圖，顯示列表中的用戶在他們的環境（城市，城鎮）中移動。

所有這3點可以優化：

客戶移動10米時，以減少的數據的量來處理
「球形矩形」中MyISAM表與空間索引搜索發送他的位置（使用MBRContains）來卸載MySQL數據庫。
公共輸出文件：如果2個用戶位於x米半徑內（2個用戶彼此靠近），則發送的XML可以相同。

很難使負荷估計在這個階段，但我認爲，客戶端 - 服務器架構是不適合這種類型的應用程序和peer2peer的可能是一個很好的答案，如果當它們相互靠近2個客戶端可以通信。

我的觀點是：

是否有任何梅索德使可能的客戶到位於某一半徑沒有中央服務器的幫助下盲目搜索其他客戶端？（它可能與UDP廣播:-)

編輯：更正。 UDP Brodcast允許客戶機在任何地方，某個範圍或IP地址中輪詢機器。

感謝你的幫助，弗洛朗

來源

2012-02-19 Flo

我GOOGLE「搜索空間P2P」，發現這兩個研究（它看起來是非常複雜的空間算法和我將嘗試使用基本的客戶端/服務器架構進行操作）。 http://www.springerlink.com/content/9r6wl93g52bg6c75/ http://www.ijcaonline.org/archives/number15/315-483 – Flo 2012-02-19 20:14:54

-1

你必須有中央的同行/服務器，因爲你需要集中一些信息，以便能夠執行你的功能。

我會去如下：

指定平方英里（或任何你想要的大小）到特定的服務器。
是否有設備發送一個'我在這裏'的消息及其座標給一些調度員，他們會將這些消息轉發到正確的平方英里服務器進行處理。
服務器在設備進入他們管理的平方英里時註冊。這可能是確保設備註冊到一個且僅一個方格的中心地圖。
將此消息轉發給廣場上的所有其他設備。
並且/或者確保您包含此消息的用途，並確保設備在將其顯示給用戶之前對其進行檢查。

調整廣場的大小和'我在這裏'的消息率。而已。

來源

2012-03-11 00:28:58 JVerstry

很抱歉的批評，但是這是一個PRACTIC開發商的典型速戰速決答案它說「爲什麼我應該花時間思考我什麼時候可以花時間進行開發」，不幸的是這是行業所付出的代價。通過這種方式，您最終將得到一個與Oracle緊密結合的解決方案或其他一些通用技術，這將有助於以遠遠不能滿足的方式降低任務的複雜性。有更優雅的解決這個問題，允許找到節點的鄰居在O（日誌（N））啤酒花 – Lu4 2012-04-07 23:23:43

@ LU4這是一個笑話？您如何將地理位置與Kamdelia距離連接起來？這些完全不同。 Kamdelia距離是一個抽象的數學概念，與真實的地理位置距離無關。你根本不理解這個問題。你沒有將抽象與現實聯繫起來。 – JVerstry 2012-04-08 14:09:19

@JVestry你的現實並不真實。你打算使用的一箇中央服務器解決方案是一個嚴密的瓶頸，它是失敗的根源和萬惡之源。想象一下，它會下降，整個P2P網絡將停止工作。如何在您的架構中解決可擴展性問題，需要多少成本來擴展？安全性如何，防止黑客入侵有多安全？ JVestry我不想冒犯你，但你的解決方案是一個痛苦的屁股，就像行業解決方案一樣，你的錢不是爲了幫助你解決問題。 – Lu4 2012-04-09 10:40:50

-1

答案實際上取決於很多事情，所以我會幫助基本策略。要理解事情，您需要了解Kademlia如何工作（Kademlia是一個存儲信息的DHT P2P網絡）。

在Kademlia第一次啓動時，每個節點選取一個隨機ID，這是一個160位數字，代表所有可能的160位ID空間中的一個點。

的需要被存儲的與SHA-1函數（它接收任意字符串，並且輸出等的需要被存儲的信息ID處理160位的數目）

獲得的信息的ID之後，您將獲得信息的ID，然後將其發佈，信息將物理存儲在ID接近信息ID的節點上。

（插圖從here截取）

enter image description here

的信息被通過查詢它的ID。信息查找或節點查找都需要O（log（N））跳來獲取所需的信息。在Kademlia中使用「XOR」度量（在您的情況下，它可以是普通的歐幾里德度量）。

每個節點都維護一個存儲桶陣列，每個存儲桶包含適合當前存儲桶的節點地址。「恰當」是衡量身份證多近的標準。考慮例如：

  0        160 
Node 1 ID: 1101000101011111101110101001010... 
Node 2 ID: 1101011101011111101110101001010... 
Node 3 ID: 1101000101011001101110101001010...

施加XOR度量的節點＃1,2之後即（計算表示這些節點之間的虛擬距離的數量），我們得到：

index -
xor - 000001100000000... (the difference is in 5-th msb bit) 
order - msb   lsb

施加異或度量節點之後＃1,3我們得到：

index -
xor - 000000000000011... (the difference is in 13-th msb bit) 
order - msb   lsb

顯然節點1更接近節點3，因爲它具有比來自節點1的距離更小顯著比特差到節點2並且因此從一個PO int節點1的視圖中，它的鄰居節點3轉到第13個存儲桶（較高的索引表示更近的ID），並且節點2轉到第5個存儲桶，其中包含一組距離一個5 MSB基數的節點當前節點ID。

這樣的數據結構允許每個節點知道它在各種距離的160個級別中的環境。

回到您的示例，爲了允許高效的地理空間查詢，您需要用普通歐幾里德度量替換Kademlias XOR度量。在這種情況下，你有你自己的ID爲3D或2D向量，不幸的是由於事實與浮動它們不能直接適用於這種類型的算法的點數，所以你需要將它們轉換成離散的二進制數歐幾里德的度量結果以某種方式類似於XOR功能的方式。之後，找到節點的相鄰節點是一件小事。

希望這會有所幫助。哦，通過外觀HyperDex的方式，新的搜索分佈式檔案系統緊密聯繫在一起的歐幾里德度量，可以幫助...

來源

2012-04-08 00:45:43 Lu4

你如何連接地理定位與Kamdelia距離？這些完全不同。 Kamdelia距離是一個抽象的數學概念，與真實的地理距離無關。 – JVerstry 2012-04-08 14:10:01

鍵之間的距離是一個數字，地理位置之間的距離也是一個數字。你應該採取Kademlia的概念，把鍵換成地理位置，Xor度量到Euclidian度量，你將會像一頭大象一樣快樂。 – Lu4 2012-04-09 10:47:25

尤達，告訴我在Kamdelia鍵和地理位置之間做映射的算法。做實際的實施，並在原始問題中將解決方案插入到問題中。在途中，你會學到一些東西。到目前爲止，你只是在天空中抽菸......它會讓你的頭旋轉！得到真實！ – JVerstry 2012-04-09 12:06:43

是否可以在P2P網絡中進行空間搜索？

回答

相關問題