Ｐ２Ｐ技術在點云數據處理中的應用

摘 要：介紹了P2P技術，討論了JXTA技術及其特點，并通過研究和實驗把JXTA技術應用到點云處理中。同時指出了應用中存在的問題和未來的方向。

關鍵詞：對等網；JXTA；對等體；逆向工程；點云處理

中圖分類號：TP311文獻標志碼：A

文章編號：1001—3695(2007)03—0197—03

0 引言

P2P（Peer—to—Peer，對等網）是一種分布式系統，其主要特征[1]是自組織、對稱式通信和非中心化控制。自組織P2P網絡能夠在對等體進入、離開和失效時自動加以調整適應[2]。對等體之間的通信是對稱的，它們既請求服務又提供服務。非中心化控制即P2P網絡沒有集中的目錄或控制點，對等體自主進行控制。目前P2P技術研究和應用中具有代表性的項目包括Gnutella[3]、Freenet[4]、Pastry[2]、Tapestry[5]、Chord[6]、pSearch[7]等。

P2P技術是計算機應用技術和網絡普及到一定程度的必然產物[8]。隨著時代的發展，網絡環境中閑置的資源不斷增加；與此同時科學計算卻呈現出計算密集型的趨勢，需要耗費海量的存儲和計算資源。人們希望把一個國家或地區的超級計算機系統整合為一個統一的計算平臺，使用戶可以像使用一臺單機那樣來完成計算密集型任務。20世紀90年代網格計算由此興起，不過其基本模型仍是客戶/服務器模式。受網格計算的啟發，為了充分利用Internet邊緣資源（包括存儲、計算、內容等），提出了全分布式通信模型為基礎的P2P技術，以便有效地利用大量個人閑置資源，并向用戶提供各種網絡計算服務。從目前的應用來看，P2P的優勢主要體現在大范圍的共享和搜索上，并集中在以下幾個方面：對等計算、協同工作、搜索引擎和文件交換。其中對等計算是本文研究的重點。

逆向工程是一種從模型對象表面獲得的點云數據出發，人工或自動生成一個已存在模型實物的替代品的技術。逆向工程經常要進行頻繁而又大量的點云處理，而各種點云處理算法幾乎都基于最近點計算，即要在幾十萬甚至幾百萬的點云數據中找出距離某個點最近的一百個或更多個點。最近點計算通常要耗費大量計算時間，以致無法付諸實際應用。如何提高計算速度？在不增加硬件投資的前提下，充分利用局域網內已有的資源進行P2P分布計算成為一個可行的解決方案。

JXTA[9]是一個用來解決P2P計算的開放網絡計算平臺，它被設計成獨立于編程語言和系統平臺，同時使用了易于實現和集成到P2P服務及應用的協議。經過五年多的發展，JXTA已變得愈加穩定且高效，因此本文選擇JXTA技術實現基于P2P的分布式計算在點云數據處理中的應用。

1 P2P分布式計算模式和實現

1.1 P2P分布計算平臺

局域網中P2P分布計算平臺體系結構如圖1所示。

該平臺采用要進行點云處理的機器作為調度管理器，局域網內其他機器作為工作端一起進行協同計算。P2P分布計算平臺主要由調度服務器、數據服務器和工作端三部分組成。此處調度服務器也充當數據服務器的角色。調度管理器負責任務的劃分和分派，以及計算結果的管理和后處理；工作端請求并接收由調度管理器分派的子任務。由于局域網的拓撲結構簡單，一個網絡內只設置一個調度管理器，工作端不再對子任務進行進一步劃分和分派，而是直接進行計算并在完成后返回結果。

1.2 JXTA技術體系結構

JXTA技術是一套開放的通用P2P協議，支持連接到網絡上任何設備之間的通信和協作。其特點是高度的互操作性、平臺無關性及通用性等。JXTA協議獨立于底層實現，不依賴特定的編程語言和操作系統，也不依賴特定的網絡傳輸機制和拓撲結構，以及特定的認證、安全或加密模型。目前比較成熟的JXTA參考實現有J2SE、J2ME和C語言版本。本文采用最新的J2SE版本。

如圖2所示，JXTA軟件架構可以分為三層[10]。最底層為平臺層，也稱JXTA核心，實現構建P2P應用的關鍵機制，包括發現、傳輸及對等體和對等組的創建等；中間層為服務層，提供搜索、索引、目錄、存儲系統、文件共享、資源聚集、認證等網絡服務，它不是P2P網絡運行所必需的，但通常不可或缺；最頂層為應用層，包括集成應用的實現，如P2P即時通信、文檔和資源共享、娛樂內容管理和分發等。

圖2 JXTA軟件架構

JXTA的核心概念[11]包括對等體、對等組、網絡服務、模塊、管道、通告、消息和標志符等，通過這些組件及協議就可以實現對等體之間的通信和協作、對等組提供服務和傳播消息并處理回應等功能。其中消息是對等體之間數據交換的基本單元，不同服務之間通過管道來發送或接收消息。JXTA使用了二進制格式的消息來保證二進制或XML數據的高效傳輸。下面論及的子任務就是通過封裝在消息中進行派發的。

1.3 最近點計算任務的劃分

單機上進行最近點計算的算法一般是：①確定需要進行最近點計算的點，如點T；②計算點云數據中其他點到點T的距離；③對計算所得結果即距離進行排序；④取得離點T距離最近的一定數量，如100個點數據。取得這些最近點之后就可以對點云數據進行下一步處理。當點云數據量大至百萬甚至數百萬，又需要頻繁進行最近點計算時，即使單機的全部資源都用于計算，仍會在時間上造成不可忍受的滯后，于是考慮把計算分布到多臺計算機上。

要進行分布式計算，計算任務必須是可劃分的。點云數據的特點是一個點由一行數據表示，包括點的XYZ三維坐標或顏色等附加信息，這使得計算任務的劃分變得相對簡單。根據這個特點，可以通過指定行的范圍來劃分任務，如圖3所示。假設需要對200萬個點云數據進行最近點計算，可以把整個任務劃分為五個子任務，分布在五個工作端上進行計算。其中子任務的算法為：①向調度管理器發出請求并取得需要進行最近點計算的點，如點T，以及點云數據范圍，如0和399 999即1—40萬行這一區段；②計算該點云數據范圍內所有點到點T的距離；③對計算所得結果進行排序；④取得離點T距離最近的一定數量，如100個點數據并發送至調度管理器。

所有子任務計算完成后，調度管理器便對取得的5×100個最近點進行排序得到最終結果。子任務處理的點云數據量需要在計算時間和工作端與管理器通信協調開銷之間進行平衡，并根據整個網絡的工作端數量進行劃分和調整。

1.4 基于JXTA的分布計算

本文選用JXTA的Java綁定來實現分布計算，由此也可以利用Java語言提供的許多便利，如跨平臺、快速開發等。

點云處理中最近點計算任務可以劃分為四部分，即任務分解、任務派發、子任務求解和結果處理。除子任務求解由工作端處理外，其他三部分均由調度管理器完成。基于JXTA的分布計算過程主要包括如下幾個步驟：

（1）點云數據文件的布置及分布式計算環境搭建

首先把點云數據文件的副本分別拷貝至調度管理器和所有工作端；然后將需要進行點云處理的機器作為調度管理器，搭建整個調度管理框架；在工作端布置并啟動工作端應用程序。

（2）計算任務的分解和派發

調度管理器對點云數據文件進行統計取得任務計算量，根據調度管理器和工作端之間通信時間的10—20倍計算時間為子任務計算量來劃分計算任務，并根據子任務數量創建一個子任務隊列TASK[0，…，m]和一個結果隊列RES[0，…，m]，分別存儲子任務0，1，…，m的計算條件和計算結果。

JXTA應用程序必須先找到并加入NetPeerGroup對等組，每個JXTA對等體都屬于NetPeerGroup。局域網內所有計算機都將參與分布計算，因此不建立專用對等組，而是直接采用這個缺省對等組。調度服務器加入NetPeerGroup，完成上述初始化工作后在對等組里發布一個輸入管道通告，并根據這個通告創建一個輸入管道來監聽工作端的請求。一旦收到工作端的子任務計算請求，調度管理器立即查詢RES[0，…，m]和TASK[0，…，m]，將標記“未完成”的子任務發送給工作端。

這里的子任務實際上是一個對象，包含了計算代碼和數據指針。調度服務器發送子任務消息前先將子任務對象串行化成二進制序列，然后封裝在XML格式的消息中。工作端接收子任務消息后，將這部分二進制序列抽取出來，反串行化得到子任務對象后立刻執行。串行化和反串行化并不會影響子任務的實際代碼和功能。

（3）工作端的子任務請求和求解

工作端對等體啟動后便創建一個輸入管道供消息接收之用，并一直處于查詢通告的狀態；同時啟動一后臺守護線程，負責定時檢測系統狀態，判斷系統當前資源空閑率是否適合進行子任務求解。一旦系統資源許可并找到調度服務器發布的輸入管道通告，便創建輸出管道向調度管理器發送子任務請求消息。調度服務器輸入管道監聽到這個消息并判別其類型（整個環境內消息分為兩種類型，即子任務請求和子任務結果）；判定是子任務請求消息后，立即通過輸出管道向工作端的輸入管道發送封裝有子任務的消息。

工作端收到該消息后，抽取其中的子任務并反串行化成子任務對象，執行完成后返回結果。調度服務器接收到結果消息并對其類型進行判斷，然后把結果存入結果隊列。

（4）結果處理

調度服務器派發完所有子任務后，不斷查看結果隊列RES[0，…，m]。如有結果不符合要求或有子任務未完成計算，則重新派發需要重新計算的子任務，直到所有子任務求解完成。最后調度服務器綜合所有子任務結果并計算得到最終結果。

1.5 實驗結果

本文選取一個手機模型的點云數據（圖4）進行實驗，包含128萬個點。子任務的計算量為12.8萬個點。整個實驗環境包括一臺調度管理器和五臺工作端，軟件配置為JDK1.5。實驗結果表明，單機上平均計算時間為3.1 s，進行分布求解時平均計算時間為1.0 s，效率有大幅提高。

2 結束語

本文使用了JXTA的Java綁定實現P2P分布計算平臺，雖然具有開發快速、構造簡單等諸多優點，但是由于Java虛擬機的存在必然導致執行速度上的損失，在實際應用中選用JXTA的C綁定進行開發應該是一個更為合適的選擇。另外對工作端資源空閑率的判斷或限定工作端子任務計算量在實際應用中必須不斷加以調優。此外當局域網內的機器數量達到數十甚至數百臺時，如何實現負載均衡也是一個值得考慮和完善的問題。

隨著P2P技術的發展，以此為基礎的新應用仍將層出不窮，而已有的應用也會愈加成熟。這其中基于P2P的分布計算顯然是重要的組成部分之一，也將在點云處理等大計算量的工程實踐中得到越來越廣泛和深入的應用。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。