Ｐ２Ｐ技術在點云數(shù)據(jù)處理中的應用

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

關鍵詞：對等網(wǎng)；JXTA；對等體；逆向工程；點云處理

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

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

0 引言

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

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

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

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

1 P2P分布式計算模式和實現(xiàn)

1.1 P2P分布計算平臺

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

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

1.2 JXTA技術體系結構

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

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

圖2 JXTA軟件架構

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

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

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

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

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

1.4 基于JXTA的分布計算

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

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

（1）點云數(shù)據(jù)文件的布置及分布式計算環(huán)境搭建

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

（2）計算任務的分解和派發(fā)

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

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

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

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

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

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

（4）結果處理

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

1.5 實驗結果

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

2 結束語

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

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

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