翻譯以.原文和在同一文件中前

P2P網(wǎng)絡(luò)的融合而導(dǎo)致的節(jié)點的有限的傳輸范圍和節(jié)點的移動性。本文涉及三種方法在（IAL（EAL（EXL用在融合的P2P網(wǎng)絡(luò)中。在Gnu la模型中，當(dāng)一個節(jié)點P的鄰居節(jié)點的數(shù)量降低到下界值以下的時候，P點就開始與其他的點建立聯(lián)系。所以，在Gnu la模型的這個節(jié)點將進(jìn)行合并操作。在EXL方法中，一個地址自動分配協(xié)議被擴(kuò)展應(yīng)用到移動自組網(wǎng)的P2P覆蓋融合中去。通過模擬，我們發(fā)現(xiàn)EXL方法，在結(jié)構(gòu)化和非結(jié)構(gòu)化的：融合，P2P(對等)，覆蓋，移動自組網(wǎng)，跨層路由設(shè)計，地址自動分引P2PCPU、內(nèi)存和文件一樣的共享資源強(qiáng)大的、分布式的容錯網(wǎng)絡(luò)架P2P網(wǎng)絡(luò)中，一個節(jié)點隨機(jī)選擇一定數(shù)量的其他節(jié)點進(jìn)行看戲。因此，一個隨機(jī)的拓?fù)浣Y(jié)構(gòu)就在一個非結(jié)構(gòu)化的P2P網(wǎng)絡(luò)的節(jié)點中形成。非結(jié)構(gòu)化的冗余流量的關(guān)系，一個節(jié)點被設(shè)定了一個下界值(LB)和一個上界值（UB）用來控制它與其它節(jié)點的聯(lián)系。Gnula模型就是一個非結(jié)構(gòu)化P2P覆蓋的例子。結(jié)構(gòu)化的P2P網(wǎng)絡(luò)，也被稱作基于分布式哈希表（DHT）P2P，節(jié)點在覆蓋網(wǎng)絡(luò)上的分布根據(jù)DHT算法有如下幾種結(jié)構(gòu)：環(huán)形、屬性、和其它度結(jié)構(gòu)。在加入一個P2P網(wǎng)絡(luò)后，一個節(jié)點根據(jù)DHT算法在網(wǎng)絡(luò)中分配關(guān)于共享的數(shù)據(jù)項的信息。同樣，要想一個數(shù)據(jù)項，根據(jù)DHT算法從發(fā)送端信息一直查詢到它的鄰居的信息。結(jié)構(gòu)化的P2P網(wǎng)絡(luò)，非常適合需要基于搜索的應(yīng)用程序。結(jié)構(gòu)化的結(jié)構(gòu)化P2P網(wǎng)絡(luò)的]ID對應(yīng)點的IP地址或者公鑰計算。然后在覆蓋的網(wǎng)絡(luò)上基于ID連接節(jié)點，就想Chord模型[1]。第二類ID空間來連接該點和它的鄰居節(jié)點。例如，Can模型[3]P2P移動和無線技術(shù)已經(jīng)在最近取得了很大的進(jìn)展。如今的、PDA和其它手持設(shè)備具有較大的內(nèi)存，更高的處理能力和更豐富的功能。用戶可以的音頻，，Wi-Fi。（MANETMANET中的每個節(jié)點可以作為兩個主機(jī)（發(fā)送/接收數(shù)據(jù)，并且一個路由器（有配備了，PDA或其他手持設(shè)備的用戶設(shè)備，在低無線電通信的范圍內(nèi)，就可以形可以在機(jī)場候機(jī)室、音樂會、車站、火車站、大學(xué)校園和。的P2P絡(luò)，不所的節(jié)都可共和據(jù)P2P2PP2P了一些建議[7-23]。.的分割就續(xù)的撲分割成兩塊或塊不續(xù)的拓?fù)錁觾蓧K或不連續(xù)拓?fù)淇梢圆⑿纬衫m(xù)的網(wǎng)?，F(xiàn)有的動自組網(wǎng)中的2PP2P為了解決網(wǎng)絡(luò)分割問題，需要兩個步驟。首先檢測出網(wǎng)絡(luò)中被分割的發(fā)生。P2P網(wǎng)PP1從自己的鄰居節(jié)點列表中移除，然后與心得節(jié)點建立聯(lián)系。第二部分融合分割的網(wǎng)絡(luò)。當(dāng)兩個當(dāng)兩個物理網(wǎng)絡(luò)融合并開始互相聯(lián)系，這兩個P2P網(wǎng)絡(luò)的負(fù)載P2PP2P網(wǎng)絡(luò)在物理網(wǎng)絡(luò)上相連，但是在覆蓋層不相連。例如，圖1（a）所示，兩個不相連的物理網(wǎng)絡(luò)PN1和PN2PN1上有一個P2PO1,PN2上有一個P2P覆蓋O2。一段時間后，PN1PN21（b）P2PO1O2沒有建立聯(lián)系。為了檢測這種情況，P2P網(wǎng)路在覆蓋層的融合，我們提出了三種融合方法，它們有一節(jié)點可以連接網(wǎng)絡(luò)，那么將會形成一個大型的P2P網(wǎng)絡(luò)的文件共享庫。在覆蓋層融合這樣的P2P網(wǎng)絡(luò)，優(yōu)點在于可以讓的同伴來文件。另一個優(yōu)點在于小少了路中的P2P網(wǎng)絡(luò)融合的第法:IAL方法。在第三章中介紹第二種方法：EAL方法。在第四章中介紹第三種方法：跨層法（EXL。在第五章，我們介紹如何仿真及其結(jié)果。相關(guān)工一個數(shù)據(jù)項擁有一個K,在地址空間中第一個與K相等或者緊跟著K的節(jié)點就是該successor（KmmChord模型中的指針表，一個對于K的查找平均會在(logN)/2次路由跳之后可以被解決，其中Nnsuccessor（n）的探查信息來間的節(jié)點的突然鄰居信息。在Can模型中對K進(jìn)行路由查詢的話，一個節(jié)點P查徑長度達(dá)到(D/4)*(N/D)路由跳，其中D是地址空間的維度，N是系統(tǒng)點的個數(shù)。Diego[9]在弦算法的基礎(chǔ)上提高了效率，通過提供文件查詢的多余信息來避免由于頻繁丟失查詢包導(dǎo)師的包的。Dewan[10]把整個網(wǎng)絡(luò)分成不同的區(qū)域并且選出點保存在一起。M-Chord算法[12]把弦算法應(yīng)用到了移動多跳網(wǎng)絡(luò)。M-Chord把節(jié)點分RIGS（環(huán)區(qū)間圖形搜索）自組網(wǎng)上的P2P網(wǎng)絡(luò)層的融合問題。Gnula模型是最早的在網(wǎng)上文件的分布式P2P系統(tǒng)之一。為了加入GnulaP2PGnula-connect請求建立聯(lián)系。如果被聯(lián)絡(luò)的點可以接要在Gnula模型中確定一個數(shù)據(jù)項的位置，一個節(jié)點把查詢信息在整個覆蓋網(wǎng)絡(luò)上泛洪，查詢信息里含有包含數(shù)據(jù)項的關(guān)鍵信息和數(shù)列的號碼。Query-hit消息在查詢路接到query-hit信息后，請求的節(jié)點直接傳遞數(shù)據(jù)項到指定的源節(jié)點。P2P網(wǎng)絡(luò)中的一些方法[15-18]沒有在覆蓋網(wǎng)絡(luò)中保存。文件查找的請點的ID也返回源節(jié)點路由?；诜汉榈姆椒ㄐ实投也⑶夷芰Σ頪26].Macro提出了一個叫做XL-Gnula的跨層的方法，這個方法基于路由協(xié)議OLSR[24].中介中得到關(guān)于物理網(wǎng)絡(luò)中最近的節(jié)點的信息然后與它們聯(lián)系。XL-Gnula也提供物理連接網(wǎng)絡(luò)的拓?fù)?。XL-Gnula也沒有考慮到P2P網(wǎng)絡(luò)的分割和融合。Leonardo在Gnula算法和弦算法的基礎(chǔ)上做了改進(jìn)，運用了不同的潛在的活性的積極地路由協(xié)議。他們發(fā)現(xiàn)Gnula算法和弦算法如果以AODV作為基礎(chǔ)協(xié)議的話會表現(xiàn)的更好這也就是AODV能作為移動自組網(wǎng)上的P2P網(wǎng)絡(luò)的基礎(chǔ)路由協(xié)議的原因。Diego[9]通過Gossi[27]路由協(xié)議優(yōu)化了非結(jié)構(gòu)化的P2P網(wǎng)絡(luò)。他們根據(jù)網(wǎng)絡(luò)路徑計算傳遞的可能性，這樣的話，傳遞的路線就會減少。運用蜂窩的方法，P2PSI[13]數(shù)據(jù)集和信息表格。信息表格包含每一個數(shù)據(jù)集文件的路由信息。P2PSI當(dāng)節(jié)點村相互P2P網(wǎng)絡(luò)可以有如下點P的狀態(tài)變聯(lián)系狀，P點開始編的渴到P物理網(wǎng)絡(luò)中運用擴(kuò)展的環(huán)搜索（ES）算法廣播請求，為了能與更近的新節(jié)點建立聯(lián)系。在點P的P2P部分立的聯(lián)。此，Gu la算法的P2P當(dāng)入P2P的個P2PL在P2P網(wǎng)覆層合的候是L有下幾。先L個P2P網(wǎng)絡(luò)融合過中表的常慢。二，L方法當(dāng)他們在物理網(wǎng)絡(luò)變得連接的時證PPL適用的動、和割生的絡(luò)。P2P網(wǎng)絡(luò)不能完P(guān)2PPP1沒有聯(lián)系的時候，P點為了恢復(fù)就會廣播P1點沒有聯(lián)系的信息。如果P點沒有收到P1點的回復(fù)，PP1P2PP1點的鄰居建立聯(lián)系。顯示應(yīng)用層法在顯示應(yīng)用層法中，我們把P2P網(wǎng)絡(luò)中的一個節(jié)點當(dāng)做根節(jié)點來標(biāo)識這個P2P網(wǎng)絡(luò)。P2P網(wǎng)絡(luò)中。KLIVEP2PIDKLIVE信息時，一個沒在根節(jié)點是按照如下方法被選出的。第一個加入網(wǎng)絡(luò)的點成為根節(jié)點。當(dāng)P2P網(wǎng)絡(luò)中的根節(jié)點不能聯(lián)系的時候，新的根節(jié)點按照如下方法選出。當(dāng)一個節(jié)點P沒有接到來自根節(jié)（REPKTP與根節(jié)點之間的距離。物理上靠近根節(jié)點的點有機(jī)會成為新的根節(jié)點。P點發(fā)出的REPKT信息包含無法聯(lián)絡(luò)的根節(jié)點和P點與失聯(lián)的根節(jié)點的距離。與失聯(lián)的根節(jié)點距離相近的節(jié)點P被選作新的根節(jié)點。根節(jié)點P1的失聯(lián)可能是由于節(jié)點的移動性導(dǎo)致的，或者P1可能離開了P2P網(wǎng)絡(luò)，或者P1被關(guān)閉。當(dāng)一個節(jié)點P接到了兩個不同的根節(jié)點發(fā)來的KLIVE信息，P點檢測出有另一個P2P網(wǎng)絡(luò)的分支存在，在這個分支里，PP點可以再物理網(wǎng)絡(luò)上到達(dá)P2P網(wǎng)絡(luò)。P點通過如下方法進(jìn)行合并操作。為了避免冗余傳輸，P點在合并操作IDPID。這樣的話，ID通過廣播合并請求信息（MRQST）進(jìn)行合并操作，并且把P等待隨機(jī)的時間來進(jìn)行合并操作。這PP2PPP1收到了同樣的包含P的根節(jié)點ID，新的P2P分支的根節(jié)點ID和P點到新的P2P分支的根節(jié)點的距離。PP2MRQSTP2P的根節(jié)點，然后P點發(fā)送合并回復(fù)信息（MRPLY）MRQSTP2P所存在的P2P網(wǎng)絡(luò)的新的根節(jié)點會在網(wǎng)絡(luò)上發(fā)布的根節(jié)點的修改信息以便網(wǎng)絡(luò)中所有點的根節(jié)點ID是一樣的。Gnula的融P點正處于飽和狀態(tài)，PP點接受新的P2P網(wǎng)絡(luò)中物理上更近的節(jié)點的MRPLY，并建立連接。在接到P2傳來MRPLY信息出請P通過連接一P2P網(wǎng)絡(luò)里的物理上更近的節(jié)點來加入新P2P網(wǎng)絡(luò)。但P點還保存著與原有的P2P分支的可連接性。在這個時候，PP2P網(wǎng)絡(luò)之間的橋梁。ChordCanChordPP2P網(wǎng)絡(luò)時，PP2P網(wǎng)絡(luò)上的后繼當(dāng)P的前驅(qū)和后繼節(jié)點都加入了P2P網(wǎng)絡(luò)后，P點離開現(xiàn)在的P2P網(wǎng)絡(luò)并改變橋的屬性。對于Can模型來說，當(dāng)P點加入新的P2P網(wǎng)絡(luò)然后把它的狀態(tài)改為橋，然后P點通知它直接相連的鄰居節(jié)點去加入新的網(wǎng)絡(luò)。當(dāng)P點的所有鄰居都加入了新P2P網(wǎng)絡(luò)之后，P點離開現(xiàn)在P2P為網(wǎng)絡(luò)然后改變橋的狀態(tài)。這樣的節(jié)點的與其他普通節(jié)點的離開不同，它會一直持續(xù)到整個存在的網(wǎng)絡(luò)都P2P網(wǎng)絡(luò)。一個橋狀態(tài)的節(jié)點繼續(xù)P2P網(wǎng)絡(luò)。它會幫助聯(lián)系大的在檢查了物理網(wǎng)絡(luò)分支的融合之后，EAL方法和XL方法在層的融合方法如下。MANETChordN1N2P2P網(wǎng)絡(luò)。2（a）所示，假N2P2N1P2變?yōu)闃虻臓顟B(tài)。如2（b）所示。然P2通知前去借P4和后繼節(jié)P8.P8P4加入網(wǎng)N1然后通知他N2P2P網(wǎng)絡(luò)后，P2N1網(wǎng)絡(luò)然后改變橋的狀態(tài)，如2（c）所示。淚滴的，P6加入N1,N1N2融合后你，最后的覆蓋網(wǎng)絡(luò)如圖2(d)。2Chord加入N1當(dāng)P2得知它的所有鄰居節(jié)點都加入了N1后，P2離開N1并改變橋狀態(tài)圖（N1和N2融合后，最后的網(wǎng)絡(luò)如圖3（d）所示。3Can顯示跨層MANET里的地址自動分配的方法有以下幾種[28-33].這些方法根據(jù)應(yīng)用方案的不同都各有優(yōu)缺點。Yuan提出了一個基于者方法的自動地址分配，這種方法被稱作最佳（ODACPID。AA的作用是探查網(wǎng)絡(luò)分割和融合。AA也持有在它的的更加有活性和們運用ODACP方法去進(jìn)行檢測盒融合P2P網(wǎng)我們考慮到一個點的加入與一個P2P網(wǎng)絡(luò)的加入是不同的。前者通過一個點加入網(wǎng)絡(luò)為了獲取有效地唯一的地址。后者一個已存在的點想要加入一個P2P網(wǎng)絡(luò)的過程。地P2P網(wǎng)絡(luò)的方法都認(rèn)為點的唯一地址是固定分配的，忽略了移動地址分配。EXL方法的細(xì)節(jié)如下。在檢測物理網(wǎng)絡(luò)分支的合并的基礎(chǔ)上，地址分配的改變問題在ODACP中被解決，通過改變擁有更少量的點的分支的地址來解決。這將會減少在網(wǎng)絡(luò)融合過程中的路由過載。但是在應(yīng)用層的P2P網(wǎng)絡(luò)必須增加額外的項目來用于P2P的少量的點改變它們的網(wǎng)絡(luò)ID變成新的物理分支的ID，然后在物理網(wǎng)絡(luò)上廣播改變點ID的信息（CNID。CNIDAAIDAAID。我們猜想，每一CNIDID。當(dāng)收到接受信息的時候，一個節(jié)點檢查它的鄰居節(jié)點的ID的改變，然后用新的IDID，但是舊的ID仍然保持一段時間。這樣的話，所有點都了解了鄰居節(jié)點新的ID信息。CNID之后，一個節(jié)點通過跨層結(jié)構(gòu)通知應(yīng)用層。通知的內(nèi)容包括CNIDPP2P網(wǎng)絡(luò)上廣播融合請求信息|（MRQST）來開始融合操作。隨機(jī)等待的時間取決于P點與新的AA的物理性。PMRQST后，P1執(zhí)行如下操作。、PAAP1AA一樣，P1AAPP1P1MRPLYP按照結(jié)構(gòu)化和非結(jié)構(gòu)化的方法進(jìn)行融合操數(shù)學(xué)分包的數(shù)量。通過這樣來檢測在覆蓋層的P2P網(wǎng)絡(luò)的融合，公式如下。T(n)=D(n)+f? 在公式（1）D(n)代表檢測P2P網(wǎng)絡(luò)融合的時候產(chǎn)生的通信量nM(n)代表在應(yīng)用層的P2P網(wǎng)絡(luò)融合產(chǎn)生的通信量f是在覆蓋層發(fā)生融合的頻率都是一樣的。因為在三種方法的檢測工作完成后，像3.13.2一樣，這三種方法IAL因為在IAL里沒有明確的結(jié)構(gòu)去檢測P2P網(wǎng)絡(luò)在覆蓋層的融D(n)=0,所以公T(n)=f? f的值小的話，會導(dǎo)致T(n)值得減小EALD(n)=

)?(n? 在這里，TotalTime表示一個網(wǎng)絡(luò)操作和活躍的總時間，TimeInterval代表從根節(jié)點廣播的KLIVE信息后的延遲。因此，代入公式得出T(n)=(TotalTime)?(n?1)+??? EXLEXL來說，不需要額外考慮在檢測中的通信量。因此D(n)=0,所以T(n)=f? EXL算法，fIALIALEXL算法。EXL算法在檢測融合發(fā)生的時候，會導(dǎo)致低的錯誤消極概率。詳細(xì)的會在第六章仿真過我們NS-2模擬器[44]進(jìn)行仿真，來比較我們的幾種方法，我們運用AOVD來作為覆蓋路由。我們使用ODACP作為自動地址分配算法在網(wǎng)絡(luò)中。仿真的參數(shù)見表格1.1圖4顯示了三種方法（IAL,EAL,EXL）的路由通信量隨著節(jié)點的移動速度的變化的生了的通信量。圖4也顯示了隨著同類點的比率的增加路由的通信量也隨著增加， 圖4在Gnula模型下三種方法的路由開但是，圖4表明，與EXLEAL相比，IAL產(chǎn)生更少的通信量。這是因為，IAL方法測P2P網(wǎng)絡(luò)的融直到這些分支成為物理網(wǎng)絡(luò)的一部分為止。而EXL和EAL方法方法產(chǎn)生更大的通信量。EALEAL算法中，一個根節(jié)點在P2P網(wǎng)絡(luò)的融合過程中周期性的播報KLIVE信息，直到融合完成。圖5在Gnula模型下三種方法的錯誤消極5中可以看出，EXLEALFN率。這是因為，EXLEAL方法有著更高的FN率，應(yīng)為IAL算法不能確保真正的融合的發(fā)生直到兩個網(wǎng)絡(luò)合并完成為止。通少融合是的路由通信量，EXL方表現(xiàn)的更好更持久根據(jù)第二章的討論結(jié)果，IALP2P6展示了所有方法的路由開銷。隨著同類點的比例的增加而增加。這是因為在保大量的開銷。圖6可以看出,EXL在兩種模型下的路由開銷少于EAL算法。這是因為在EALP2PKLIVE信息，直到融合完成。從圖六中也可以看出，CanChord模型。這的節(jié)點ID都要通過哈希函數(shù)到IP地址。然后與節(jié)點ID最近的鄰居建立聯(lián)系。因的節(jié)點聯(lián)系，一個節(jié)點P找到他的鄰居節(jié)點P1,然后通過分開P1的空間來加入。為了保持一個節(jié)點與大量的節(jié)點之間的聯(lián)系，會產(chǎn)生大量的路由開銷。因此，Can模型的路由Chord模型。通過減少路由開銷，Can模型可以在網(wǎng)絡(luò)中表現(xiàn)的更良好、更6P2P信量和包時產(chǎn)生的延遲，同樣，通過增加節(jié)點移動速度，網(wǎng)絡(luò)拓?fù)涞念l繁改變會產(chǎn)P2P網(wǎng)絡(luò)中，EXLFNEAL方法。因為EAL方法比EXL方法有著更高的通信開銷。高的通信開銷導(dǎo)致了的包的。而且，CanFNChordFNChord模型7P2P總物理網(wǎng)絡(luò)的分割和融合會導(dǎo)致在P2P覆蓋層上的P2P網(wǎng)絡(luò)的分割和融合?，F(xiàn)有的P2PIALALXL絡(luò)上，EXL算法在路由開銷和FN比率上都優(yōu)于其他兩種算法。來會在P2P網(wǎng)絡(luò) 參考文I.Stoica,R.Morris,D.Karger,M.F.Kaashoek,andH.Balakrishnan.(2001)Chord:Ascalablepeer-to-peerlookupserviceforinternetapplications,inProceedingsoftheACMM01Conference,SanDiego,California,USA,August2001,pagesA.RowstronandP.Druschel.(2001)Pastry:Scalable,decentralizedobjectlocationandroutingforlarge-scalepeer-to-peersystems,IFIP/ACMInternationalConferenceonDistributedSystemsPlatforms(Middleware),Germany,November2001,LectureNotesinComputerScienceVolume2218,pages329–350.SylviaRatnasamy,PaulFrancis,MarkHandley,RichardKarp,ScottShenker(2001)AScalableContent-AddressableNetwork,InProceeding M’01,August27–31,2001,SanDiego,California,USA,pages161–172.M.Ripeanu,I.Foster,A.Iamnitchi.(2002)MaptheGnu laNetwork:PropertiesofLarge-ScalePeer-to-PeerSystemsandImplicationsforSystemDesign,IEEEInternetComputing,volume6,no.1,pages50–57,IEEE.E.Meshkova,J.Riihijrvi,M.Petrova,P.Mhnen.(2008)Asurveyonresourcediscoverymechanisms,peer-to-peerandservicediscovery puterNetworks,volume52,no.11,August2008,ISSN:1389-1286,pages2097–2128,Elsevier..htmlJune17,G.Turi,M.Conti,E.Gregori.(2005)ACrossLayerOptimizationofGnulaforMobileAdhocNetworks,InProceedingoftheACMMobiHocSymposium,Urbana-Champain,May2005,pages343–354.LeonardoB.Oliveira,I.G.Siqueira,A.F.Loureiro(2005)Ontheperformanceofadhocroutingprotocolsunderapeer-to-peerapplication,JournalofParallelandDistributedComputing,volume65,no.11,November2005,pages1337–1347,Elsevier.DiegoN.daHora,DanielF.Macedo,LeonardoB.Oliveirac,IsabelaG.Siqueira,A.F.Loureiro,JosM.Nogueira,GuyPujolle(2009)Enhancingpeer-to-peercontentdiscoverytechniquesovermobileadhoc puterCommunications,Journal,volume32,no13–14,August2009,pages1445–1459,Elseveir.DewanTanvirAhmed,ShervinShirmmadi.(2007)Multi-LevelHashingforPeer-toPeerSysteminWirelessAdHocEnvironment,InProceedingoftheIEEEWorkshoponMobilePeer-to-PeerComputing,WhitePlains,NY,USA,March2007,pages126–131.RaphalKummer,PeterKropf,PascalFelber.(2006)DistributedLookupinStructuredPeerto-PeerAd-HocNetworks.InProceedingoftheOTMConferences,volume2,October29,November3,2006,Montpellier,France,pages1541–1554.MinLi,EnhongChen,PhillipC-ySheu.(2006)AChord-BasedNovelMobilePeer-to-PeerFileSharingProtocol,InProceedingof8thAsia-Pacificwebconference,Harbin,China,January16–18,2006,LectureNotesinComputerScience,volume3841,pages806–811.[13]R.HHwangandC.CHoh(2009)Cross-layerdesignofP2Pfilesharinermobilead munSystems,June2009,October2009,volume42,no.1–2,pages47–61,[14]H.Sozer,M.Tekkalmaz,I.Korpeoglu.(2009)APeer-to-PeerFileSearchandDownloadProtocolforWirelessAdHoc puterCommunications,January2009,volume32,no.1,pages41–50,Elsevier.[15]A.Klemm,C.Lindemann,andO.Waldhorst(2003)Aspecial-purposepeer-to-peerfilesharingsystemformobileadhocnetworks,InProceedingoftheMADNET2003,SophiaAntipolis,France,March2003,pages.41–49.[16]A.Duran,C.Chung,MobileadhocP2Pfilesharing.(2004)InProceedingoftheWirelessCommunicationsandNetworkingConference,WCNC.2004volume1,pages114–119,AbadaA.,LiCui,C.Huang,H.HChen.(2007ANovelPathSelectionandRecoveryMechanismforMANETsP2PFileSharingApplicationsInProceedingofthe 2007,,pages3472–3477,IEEE.NadirShah,DepeiQian.(2009)Context-AwareRoutingforPeer-to-PeerNetworkonMANETs,IEEEInternationalConferenceonNetworking,Architecture,andStorage,2009,ZhangJiaJie,China,pages135–139,IEEE.[19]U.Lee,J.SPark,S.HLee,W.W.Ro,G.Pau,M.Gerla(2008)EfficientPeer-to-peerFileSharingusingNetworkCodinginMANET,JournalofCommunicationsandNetworks(JCN),volume10,no.4,November2008,pages422–429.MinhoShinandWilliamA.Arbaugh.(2009)EfficientPeer-to-PeerLookupinMultihopWirelessNetworks,KSIITransactionsonInternetandInformationSystems,February2009,volume3,no.1,pages5–25.NadirShahandDepeiQian.(2010)AnefficientstructuredP2PoverlayoverMANET,MobiDE,NinthInternationalACMWorkshoponDataEngineeringforWirelessandMobileAccess(inconjunctionwithSIGMOD/PODS2010),napolis, na,USA,June2010,pages57–64.NadirShahandDepeiQian.(2010)AnefficientoverlayforunstructuredP2PfilesharingoverMANETusingunderlyingcluster-basedrouting,KSIITransactionsonInternetandInformationSystems,volume4,no.5,October,30,2010,pages799–818.NadirShah,DepeiQian(2010)ANewCross-LayerUnstructuredP2PFileSharingProtocoloverMobileAdHocNetwork,T.H.KimandH.Adeli(Eds.):AST/UCMA/ISA/CAN2010,LNCS6059,Springer-VerlagBerlinHeidelberg2010,ISBN978-3-642-13576-7,pages[24]T.ClausenandP.Jacquet.(2003)OptimizedLink-StateRoutingProtocol,IETFRFC-3626,October2003.[25]C.Perkins,E.Belding-Royer,andS.Das.(2003)AdhocOn-DemandDistanceVector(AODV)Routing,IETFRFC3561.[26]A.Helmy,S.Garg,P.Pamu,N.Nahata.(2005)CARD:AContact-basedArchitectureforResourceDiscoveryinAdHocNetwork,MobileNetworksandApplications(MONET),volume10,no.1–2,pages99–113,Springer.Hedetniemi,S.M.,Hedetniemi,T.S.andLiestman,A.L.(1988)Asurveyofgossiandbroadcastingincommunicationnetworks,Network,volume18,no.4,pages319–349,Perkins,C.,Malinen,J.T.,Wakikawa,R.,Belding-Royer,E.M.,Sun,Y.(2001)Ipaddressauto-configurationforadhocnetworks.IETFdraftRFC2026.Fazio,M.,Villari,M.AndPuliafito,A.(2006)AIPAC:AutomaticIPaddressconfigurationinmobileadhocnetworks,ComputerCommunications,volume29,no.8,pages1189–1200,Elsevier.AbhishekP.T.andPatnaik,L.M.(2008)Anaddressassignmentfortheautomaticconfigurationofmobileadhocnetworks,alandUbiquitousComputing,volume8,no.1,pages47–54,Springer.WenigerK.,PACMAN.(2005)Passiveautoconfigurationformobileadhocnetworks.JournalonSelectedAreasinCommunications,volume23,no.3,pages507–519,IEEE.Tinghui,X.andJie,W.(2007)QuorumBasedIPAddressAuto-configurationinMobileAdHocNetworks,Proceedingsofthe27thInternationalConferenceonDistributedComputingSystemsWorkshop,Toronto,Ontario,Canada2007,pages1–8.Yuan,S.andElizabethM.B.R.(2004)AStudyofDynamicAddressingTechniquesinMobileAdhocNetworks,WirelessCommunicationsandMobileComputing,volume4,no.3,pages315–329,Wiley.Ritter,H.,Winter,R.,Schiller,J.(2004)APartitionDetectionSystemforMobileAdHocNetworks,FirstIEEECommunicationsSocietyConferenceonSensorandAdHocCommunicationsandNetworks(SECON2004),October,SantaClara,California,USA,pages489–497,IEEE.Abdelouahid,D.,Nadjib,B.andAbdelmadjid,B.(2005)APartitionPredictionAlgorithmforServiceReplicationinMobileAdHocNetworks,ProceedingsoftheSecondAnnualConferenceonWirelessOn-demandNetworkSystemsandServices,St.Moritz,Switzerland,pages236–245.Karen,W.andBaochun,L.(2002)EfficientandGuaranteedServiceCoverageinPartitionableMobileAd-hocNetworks,ProceedingsofIEEE 2002,NewYorkCity,NewYork,USA,volume2,pages1089–1098,IEEE.Hauspie,M.,Simplot,D.andCarle,J.(2003)Partitiondetectioninmobileadhocnetworksusingmultipledisjointpathsset,inProceedingsof2ndIFIPMediterraneanAdHocNetworkingWorkshop,2003,pages25–27.Bratislav,M.,Nikola,M.andMiroslaw,M.(2003)PredictionofPartitioningLocationAwareMobileAdHocNetworks,Proceedingsofthe38thAnnualHawaiiInternationalConferenceonSystemSciences(HICSS’2005)–Track9,IslandofHawaii(BigIsland),pages306c.NadirShah,DepeiQian.(2010)Cross-LayerDesignforMergingofunstructuredP2PNetworksoverMANET,ProceedingofThe5thInternationalConferenceonUbiquitousInformationTechnologies&Applications(CUTE2010),Sanya,Hainan,China,pages1–7,NadirShah,DepeiQian.(2010)Cross-LayerDesigntoMergeStructuredP2PNetworksoverMANET,Proceedingof16thInternationalConferenceonParallelandDistributedSystems(ICPADS2010),Shanghai,China,page851–856,IEEE.NadirShah,DepeiQian.(2012)MANETadaptivestructuredP2Poverlay,Peer-to-PeerNetworkingandApplications,volume5,no.2,pages143–160,Springer.LeeS-B,WongSHY,LeeK-W,LuS.(2011)Contentmanagementinamobileadhocnetwork:opportunisticstrategy,Proceedingof 2011,Shanghai,China,pages266–270,IEEE.[43]I.Stojmenovic,D.S.Ryl,A.Nayak.(2011)TowardScalableCutVertexandLinkDetectionwithApplicationsinWirelessAdHocNetworks,IEEENetwork,volume25,no.1,pages44–48.AdHoc&SensorWirelessNetworks,Vol0,pp1–24 ?2012OldCityPublishing,IncReprintsavailabledirectlyfromthepublisher PublishedbylicenseundertheOCPScienceimprint,Photocopyingpermittedbylicenseonly amemberoftheOldCityPublishingGroupMergingofP2POverlaysoverMobileAdHocNetwork:EvaluationofThreeApproaches?NADIRSHAH1,2,DEPEIQIAN1ANDRUI:d ,rui.wan:Received:October9,2012.Accepted:March25,Peer-to-peer(P2P)networkisarobustanddistributedarchitectureofsharingresources.Recently,severalapproacheshavebeenproposedforP2PnetworksoverMANET.TheexistingapproachesforP2PnetworksoverMANETsdonotconsiderthemergingofP2PnetworkswhichdesignsthreeapproachestodetectandmergeP2Pnetworksatover-laylayerinmobileadhocnetwork(MANET).Theseapproachesareimplicitapplication-layer(IAL),explicitapplication-layer(EAL)andexplicitcross-layer(EXL)approaches.InIALapproach,thefollowingpropertyofGnulaisusedtomergeP2Pnetworks.InGnula,whenthenumberofneighborpeersofapeerPdropslowerthanthelowerboundvalue,thepeerPstartstoconnectwithotherpeers.SoduringthisphaseinGnula,apeermayconnectwithneighborpeersofanotherP2Pnetworkpartition.InEALapproach,onepeerisusedasaroot-peerwhichidentifiestheP2Pnetwork.Sowhenapeerdetectsmorethanoneroot-peerinthenetwork,thepeerinvokesmergingoperation.InEXLapproach,anaddressauto-configurationprotocolisextendedtomergetheP2PoverlaysoverMANET.Bysimulation,weshowthatoverallEXLapproachoutperformsothertwoapproachesintermofroutingoverheadandfalse-negativeratioforbothstructuredandunstructuredP2Pnetworks.Merging,P2P,overlays,MANET,cross-layerdesign,addressauto-?Thispaperistheextendedversionofpapers[39,1AHSWN-357˙V1 NadirShahetPeer-to-peer(P2P)networkisarobust,distributedandfaulttolerantnetworkarchitectureforsharingresourceslikeCPU,memoryandfiles.Theexist-ingapproachesforP2Pnetworksoverwirednetwork(Internet)[1–5]canberoughlyclassifiedintostructuredandunstructuredarchitectures[6].Eachofthemhasitsownapplicationsandadvantages.InanunstructuredP2Pnetwork,apeerestablishesconnectionwithacer-tainnumberofotherpeerschosenrandomly.ThusarandomtopologyisestablishedamongthepeersinanunstructuredP2Pnetwork.Theunstruc-turedP2PnetworkusesfloodingmechanismforresourcediscoveryintheP2Poverlay.TohavebalancebetweenlookuplatencyandredundanttrafficintheunstructuredP2Pnetwork,apeerestablishesconnectionswithotherpeersaccordingtothelowerbound(LB)andtheupperbound(UB)onthenumberofneighborpeers.GnulaisanexampleofunstructuredP2Pover-InastructuredP2Pnetwork,alsocalleddistributed-hashtable(DHT)-basedP2P,thepeersareplacedintheoverlaynetworkaccordingtotheDHTalgorithmfollowingring,treeorothermultidimensionalstructure.Afterjoin-ingtheP2Pnetwork,apeerdistributestheindexinformationofitsshareddataitemsinthenetworkaccordingtotheDHTalgorithm.Similarly,toaccessadataitem,thepeersendsthelookupquerytoitsneighborpeeraccordingtoDHT-algorithm.StructuredP2Pnetworkissuitableforappli-cationsrequiringsubject-basedsearch.TheexamplesofstructuredP2Pnet-worksincludeChord[1],Pastry[2]andCAN[3].ThetraditionalstructuredP2Psystems[1–3]canbegroupedintotwoclassesasfollows.FirstclassincludestheP2PsystemswhichcomputeanIDforeachpeerbyapplyinghashfunctiononthepeerIPaddressorpublickey.Thentheoverlaynetworkisbuiltupbyconnectingthepeersbasedonpeer-ID,e.g.Chord[1].Sec-ondclassincludestheP2PsystemswhichdistributesthedataitemIDspaceamongthepeers.ThenoverlaynetworkisbuiltupbyconnectingapeerPtoneighborpeersbasedonportionofIDspacethatPholds,e.g.CAN[3].EachoftheseclassesoftraditionalstructuredP2PnetworkswouldbehavedifferentlyinMANET.Mobileandwirelesstechnologyhasachievedgreatprogressinrecentyears.Today’scellphones,PDAsandotherhandhelddeviceshavelargermemory,higherprocessingcapabilityandricherfunctionalities.Theusercanstoremoreaudio,,textandimagedatawithhandhelddevices.Thesedevicesarealsoequippedwiththelowradiorangetechnology,likeBlue-toothandWi-Fi.Bymeansofthelowradiorangetechnology,theycancom-municatewitheachotherwithoutusingcommunicationinfrastructure(e.g.cellularinfrastructure)andformamobileadhocnetwork(MANET).EachAHSWN-357˙V1MergingofP2P nodeinMANETworksasbothahost(sending/receivingthedata)andarouter(maintainingtheroutinginformationaboutothernodes).MANETisdeployedintheplaceswhereinfrastructureiseithernotavailable,forexam-pledisasterscenario,ortooexpensive.Duetohighcapabilityofthemobiledevices,P2PnetworkscanbedeployedoverMANETcomposedofmobiledevices.TherearevariousP2PapplicationsoverthiskindofMANET.Forexample,theusersequippedwiththes,PDAsorotherhandhelddevices,communicatingthroughlowradiorange,canformaP2Pnetworkforsharingaudio/clips,pictures,filesandotherinformation.Possiblefilesharingapplicationscenarioscanbefoundatairportlounges,musiccon-certs,busstops,railwaystations,universitycampus,andcafeteria.WeconsiderthescenariosofP2PnetworkoverMANETwherenotallthenodesaretoshareandaccessthedataitems,i.e.somenodesarepeersandothersarenon-peers.ApeernodeisthememberofP2Pnetwork.Anon-peernodeisnotmemberoftheP2Pnetwork.Recently,severalschemeshavebeenproposedforP2PnetworksoverMANETs[7–23].DuetolimitedradiorangeandmobilityofnodesinMANETs,thenetworkpartitionandmergingofnetworkscanoccurfrequently.Networkpartitionisthebreakdownofaconnectedtopologyintotwoormoredisconnectedtopology[34].Thenodeinonetopologycannotaccessthenodeinothertopology.Similarly,twoormoredisconnectednetworkpartitionscangetmergewitheachotherform-ingoneconnectednetwork.TheexistingapproachesforP2PnetworksoverMANETdonotconsiderP2Pnetworkpartitionandmerging.TohandlenetworkpartitioninMANET,therearetwoparts.Firstoneistodetecttheoccurrenceofnetworkpartition.TheP2PnetworkpartitioninMANETcanbehandledasfollows.WhenapeerPdoesnotreceivetheprobemessagefromaneighborpeerP1,thepeerPremovesP1fromitsneighborpeerslistandestablishesconnectionwithanewpeeraccordingtooverlayrouting.Secondpartisthemergingofnetworkpartitions.Whentwophysicalnetworks(MANETs)mergebycomingintocommunicationrangeofeachother,P2Pnetworksoverthesetwophysicalnetworkswouldnotbecon-nectedatoverlaylayer.ThisisbecausethatP2Pnetworkoperatesatapplica-tionlayerasanoverlaynetwork.ThatistheseP2Pnetworkswouldbecon-atoverlaylayer.Forexample,Figure1(a)showstwodisconnectedphysicalnetworksPN1andPN2.PN1hasaP2Poverlay(O1)andPN2hastheP2Poverlay(O2).Aftersometime,PN1andPN2getconnectedinthephysicalnetworkbycomingintocommunicationrangeofeachotherasshowninFig-ure1(b).AsshowninFigure1(b),theP2Poverlays(O1andO2)arediscon-nectedatoverlaylayerthoughtheygotconnectedinthephysicalnetwork.TodetectthissituationandmergetheseP2Pnetworksatoverlaylayer,ro-posepossiblethreeapproachesinthispaper.TomergesuchP2PnetworksatAHSWN- NadirShahetFIGUREToshowP2Pnetworkpartitionatoverlaylayerwhilethephysicalnetworkislaysastheirphysicalnetworksgetconnectedisthatmorenumberofpeers(possiblyprovidingalargeportionofsharedcontents)canbereachedbyapeer.Iftherearemorepeersaccessibleinthenetworkthentherewouldbealargerandavarietyofcontent/filesaccessibleintheP2Pnetwork.TomergesuchP2Pnetworksatoverlaylayer,itsadvantageisthatonecanexploremorepeersandthusalargeportionofsharedfiles/contentscanbeaccessed.Anotheradvantageofcarryingoutmergingofoverlaysattheoverlaylayeristoreducetrafficoverhead,e.g.incaseofGnulaapeer(inconnecting-state)strivestoestablishconnectionthenewpeersbysendinglookupmessagesattheoverlaylayers,asgiveninSection2.Thusiftherearemorepeersinover-laynetwork,itwouldreducethechancesofpeersinconnecting-statewhichwouldultimayresultsinthedecreasedcontroltrafficinthenetwork.Asmentionedabove,thisveryimportantaspecthasbeenignoredbytheexistingapproaches[7-23,41,42]forP2PnetworksoverMANET.Therestofthepaperisorganizedasfollows.resenttherelatedworkandfirstapproach,IAL-approach,tomergeP2PnetworksinMANETinSec-tion2.Section3describesthesecondalternative,EAL-approach,tomergeresults.Finally,Section6concludesthepaper.RELATEDChord[1]hasthering-shapedidentifierspacehavingvaluesfrom0to2m-1,form-bitidentifier.AdataitemwithkeykisassignedtothefirstpeerwhoseAHSWN-357˙V1MergingofP2P identifierisequaltoorfollows(theidentifierof)kintheidentifierspace.Thispeeriscalledthesuccessorpeerofkeykdenotedbysuccessor(k).Ifidentifiersarerepresentedasacircleofnumbersfrom0to2m-1thensuc-cessor(k)isthefirstpeerclockwisefromk.InChord,eachpeermaintainsapointertoitssuccessorpeer.TospeedupthelookupprocessinChord,apeermaintainsadditionalpointerstothepeersintheroutingtable,calledfinger-table.Form-bitkey/identifier,apeermaintainsmentriesinitsfinger-table.Bymaintainingthefinger-tableinChord,alookupqueryforkeykcanberesolvedin(logN)/2routinghopsoage(inoverlaynetwork),whereNisthetotalnumberofpeersinthenetwork.Eachpeernperiodicallyexchangestheprobemessageswithitssuccessor(n)tomaintaintheupdatedinformation.Similarly,eachpeeralsokeepstheupdatedinformationofitsfinger-table’sentriesbyperiodicallyexchangingtheprobemessages.CAN[3]hastheidentifierspaceasamulti-dimensionaltorus.TojointheCAN,anewnodefindsanonlineexistingpeerintheP2Psystem.ThenthenewnoderandomlychoosesapointPintheidentifierspaceandsendstheJOINrequestwhichisforwardedbythepeersinCANaccordingtotheoverlayroutingalgorithm.ReceivingtheJOINrequest,apeerwhosezonecontainsPsplitsitszoneandassignshalfzonetothenewnode.InCAN,theroutingtableatapeerisofconstantsize(2entriesperdimensionifallzonesareofequalsize)andcontainstheimmediateneighborsofthepeerintheiden-tifierspace.ToroutealookupqueryforkeykinCAN,apeerPforwardsthelookupquerytoitsneighborthatisclosesttothedestination.Withthisgreedyforwardingoflookuprequests,CANachievesa agelookuppathoflength(D/4)*(N1/D)routinghops(intheoverlaynetwork),whereDisthedimensionoftheidentifierspaceandNisthenumberofpeersinthesystem.Diegoetal.[9]improvestheperformanceofChordoverMANETbyproposingredundanttransmissionsofthefile-lookupqueryinordertoavoidthefrequentlossofquerypacketsduetopacketcollision.Dewanetal.[10]dividesthewholenetworkintodifferenthomeregionsandselectsonenodeasagroupleaderineachregion.Forcontentsearchingwithinthehomeregion,theyusetheapproachsimilartotheChordwiththemodifiedfin-gertable.However,theyhavenotproperlyexplainedtheprocedureforthegroupformationandthegroupleaderselection.Kummeretal.[11]improvestheChordoverMANETbymaintainingatapeeritsphysicalcloserpeersalongwithitslogicalneighborpeers.M-Chord[12]adoptstheChordtothemobileadhocnetworks.M-Chorddividesthenodesintosuper-nodesandnormalnodes.Thesuper-nodesinM-ChordusetheproceduresimilartotheChordringtoforwardtherequesttonextsuper-nodeuntilahitorfailmes-sageisreturned.ForstaticscenariosofMANET,Shinetal.[20]proposesanapproachcalledRIGS(RingIntervalGraphSearch)whichissimilartoChord.Butunlikerandomassignmentofnode-IDinChord,RIGSAHSWN- NadirShahetthenode-IDtothepeersuchthattheassignmentgeneratesaRingIntervalGraph(RIG).Tostoretheindexinformationofsharedfilesandroutinginfor-mation,Hassanetal.[14]haveusedthedistributedhashingtable(DHT)andthetree-structurebasedonthetopologyofthenetwork.Intheirapproach,twopeerscannotcommunicateiftheircommunicationhastopassthroughintermediatenon-peernodeswhichwouldresultintheP2Pnetworkpartitionatover