移動自組網(wǎng)IP地址分配技術(shù)綜述*

蔡炎宏，馬正新

（清華大學(xué) 微波與數(shù)字通信國家重點實驗室，北京 100084）

1 引言

移動自組網(wǎng)（Mobile Ad Hoc Network， MANET）是由移動節(jié)點自發(fā)組成的多跳無線網(wǎng)絡(luò)，它的節(jié)點自由移動，網(wǎng)絡(luò)拓撲結(jié)構(gòu)動態(tài)變化。與傳統(tǒng)電信網(wǎng)和因特網(wǎng)不同，移動自組網(wǎng)是無中心的網(wǎng)絡(luò)，沒有基礎(chǔ)設(shè)施。這使得傳統(tǒng)網(wǎng)絡(luò)很多成熟的技術(shù)不能直接應(yīng)用于移動自組網(wǎng)。一直以來，對移動自組網(wǎng)網(wǎng)絡(luò)層的研究主要集中在路由方面。幾乎所有對路由的研究都假定網(wǎng)絡(luò)節(jié)點事先已配置好地址，但這一點實際上是難以做到的。對于小規(guī)模的網(wǎng)絡(luò)來說，手動靜態(tài)配置也許是可行的；但是對于大規(guī)模網(wǎng)絡(luò)，尤其是允許節(jié)點自由加入和離開的開放型、實用型網(wǎng)絡(luò)，事先配置地址是不現(xiàn)實的。而節(jié)點只有在獲得網(wǎng)絡(luò)地址以后才能進行路由和通信。但傳統(tǒng)網(wǎng)絡(luò)的地址動態(tài)配置協(xié)議不能直接應(yīng)用于移動自組網(wǎng)[1]，因此，地址動態(tài)分配是移動自組網(wǎng)實用化、商用化的一大挑戰(zhàn)。

2 地址分配技術(shù)分類評析

移動自組網(wǎng)的地址分配算法大體可分為4類。

2.1 基于狀態(tài)維護的算法

這類方法有一個共同的特點：節(jié)點維護網(wǎng)絡(luò)中地址分配的狀態(tài)信息，即已分配地址或未分配地址列表，并且通過周期性的同步更新地址分配狀態(tài)。典型的算法有MANETconf[2]和 Buddy[3]。

1）MANETconf

在該算法中，網(wǎng)絡(luò)中的每個節(jié)點都維護整個網(wǎng)絡(luò)的已分配IP地址信息，并通過泛洪的方式周期性同步更新該信息。最初網(wǎng)絡(luò)中只有1個節(jié)點，它從可分配地址空間中取1個地址作為自己的地址。隨后加入網(wǎng)絡(luò)的節(jié)點選擇它的1個鄰居節(jié)點作為配置地址的代理節(jié)點，代理節(jié)點隨后選擇1個未分配的地址（記為x），通過一種特定的消息泛洪整個網(wǎng)絡(luò)，征詢其他節(jié)點的意見，只有網(wǎng)絡(luò)中其他節(jié)點都給出肯定的答復(fù)，代理節(jié)點才將地址x分配給請求節(jié)點并更新所有節(jié)點的已分配地址表。否則，它選取另外1個地址并重復(fù)上述過程。為了應(yīng)對網(wǎng)絡(luò)的合并與分裂，該算法規(guī)定由網(wǎng)絡(luò)中地址最小者產(chǎn)生1個網(wǎng)絡(luò)標(biāo)識UUID，并泛洪整個網(wǎng)絡(luò)。當(dāng)網(wǎng)絡(luò)邊緣節(jié)點檢測到不同UUID的消息時，便檢測出了網(wǎng)絡(luò)的合并，于是交換各自的已分配地址表并處理沖突地址。網(wǎng)絡(luò)合并后，將由合并后網(wǎng)絡(luò)的地址最小節(jié)點產(chǎn)生新的網(wǎng)絡(luò)標(biāo)識。

該算法通過全網(wǎng)泛洪更新地址狀態(tài)信息，排除地址沖突，協(xié)議開銷較大；同時，每當(dāng)有新節(jié)點加入，需要等除代理節(jié)點外其他節(jié)點都給出肯定答復(fù)后，代理節(jié)點才將預(yù)選的地址分配給新加入節(jié)點，配置延時較大；此外，隨著網(wǎng)絡(luò)節(jié)點數(shù)增加，協(xié)議開銷和配置延時顯著增大，該算法的可擴展性也較差。

2）Buddy

該算法在網(wǎng)絡(luò)中的每個節(jié)點都可以為新加入的節(jié)點配置地址。最初網(wǎng)絡(luò)中只有一個節(jié)點（記為A），它擁有整個IP地址池。當(dāng)有新節(jié)點（記為B）加入時，新節(jié)點通過特定的鄰居發(fā)現(xiàn)消息選擇A作為配置節(jié)點。A將擁有的IP地址池分一半給B，B從獲得的地址池中取第1個地址作為自己的地址，同時B也擁有為其他新加入節(jié)點配置地址的能力。A，B互稱為伙伴（Buddy）。后續(xù)加入網(wǎng)絡(luò)的節(jié)點都選擇它的1個鄰居節(jié)點作為配置節(jié)點，通過類似的方式獲得該鄰居地址池的一半，并取地址池的第1個地址作為自己的地址。如果有節(jié)點無通告離開網(wǎng)絡(luò)，那么將造成IP地址的泄漏。為了處理這個問題，該算法采取了以下措施：節(jié)點間周期性地交換各自的IP地址表，不斷更新IP地址信息，以使每個節(jié)點都擁有最新的IP地址表（如表1所示）。如果某個節(jié)點發(fā)現(xiàn)它的伙伴節(jié)點不在最新的IP地址表中，則可認為該節(jié)點已經(jīng)無通告離開網(wǎng)絡(luò)，于是吸收它的地址池到自己的地址池中，以防止IP地址泄漏。

該算法需要通過泛洪方式周期性地更新IP地址表，協(xié)議開銷較大。同時，也因為周期性泛洪的存在，協(xié)議開銷隨節(jié)點規(guī)模的增大而迅速增加，可擴展性較差。但因為新加入節(jié)點只需它的鄰居節(jié)點同意即可獲得配置，無須等待網(wǎng)絡(luò)中其他節(jié)點的同意，只有兩跳延時，所以配置延時較小。而文獻[4]采取類似Buddy的方法，只是地址回收部分有所差別。

表1 IP地址表

2.2 基于沖突檢測的算法

這類算法有一個共同的特點：新節(jié)點加入網(wǎng)絡(luò)時，從整個IP地址池中隨機選取一個IP地址作為自己的地址，并通過主動或被動發(fā)現(xiàn)沖突的方式來更改地址，直到不出現(xiàn)沖突為止。主動檢測沖突的方法被稱為DAD（Duplicate Address Detection），被動檢測沖突的方法為PDAD（Passive Duplicate Address Detection）。 PMWRS[5]和PACMAN[6]是這類算法的典型代表。

1）PMWRS[5]

該算法是由Perkins，Malinen，Wakikawa，Royer 和Sun等人提出，因此稱為PMWRS算法。新加入網(wǎng)絡(luò)的節(jié)點（記為A）從169.254/16 IP地址池中隨機選擇一個地址x，并向其他節(jié)點廣播包含x的地址請求消息（AREQ）。收到該消息的節(jié)點將x與自身地址對比，如果相同，則回復(fù)消息AREP；如果不同，則不做處理。如果在計時器超時后，A沒有收到其他節(jié)點的回復(fù)消息AREP，則再次發(fā)送AREQ消息，如果在有限次嘗試（事先預(yù)設(shè)）后仍未收到AREP消息，則認為所選地址x沒有沖突，并配置該地址。否則，從地址池中重新選取一個地址，并重復(fù)上述過程。

該算法復(fù)雜度較低，容易實現(xiàn)，但存在如下缺陷：首先計時器周期的選擇非常關(guān)鍵，太短的周期會導(dǎo)致檢測不出較遠節(jié)點的沖突地址，太長的周期會導(dǎo)致配置延時過長。為保險起見，周期的選取應(yīng)該與節(jié)點的規(guī)模成正比，但這樣會帶來較大的延時。其次，如果2個新加入節(jié)點同時從地址池中抽取到同一地址，可能會引起地址沖突。此外，該方法因為通過泛洪的方式排除沖突問題，協(xié)議開銷較大，可擴展性較差。

2）PACMAN

為了避免實行DAD所帶來的大量協(xié)議開銷，該算法采用了PDAD的方式。加入網(wǎng)絡(luò)的節(jié)點按照一定的方法從地址空間中取1個地址作為自己的地址。該算法分析路由協(xié)議產(chǎn)生的數(shù)據(jù)包，通過只存在重復(fù)地址時才可能發(fā)生的事件發(fā)現(xiàn)地址沖突，并采取相應(yīng)措施處理沖突。比如在典型的鏈路狀態(tài)路由協(xié)議中，每個節(jié)點都周期性地產(chǎn)生鏈路狀態(tài)消息，該消息包含源地址、序列號等。假定每個節(jié)點的序列號都是周期性增加的，當(dāng)某個節(jié)點收到了某條鏈路狀態(tài)消息，源地址與自己地址相同，但序列號卻比自己當(dāng)前序列號大，則可確定發(fā)生了地址沖突。

該算法的優(yōu)點是在地址分配過程中不產(chǎn)生控制信息，而是通過發(fā)現(xiàn)重復(fù)地址所特有的路由事件來發(fā)現(xiàn)沖突地址并處理沖突，協(xié)議開銷較小。但該算法要求可分配地址空間比網(wǎng)絡(luò)節(jié)點數(shù)大得多，否則發(fā)生地址沖突的可能性就較大，處理沖突引入的協(xié)議開銷也會較大。此外，該算法依賴具體的路由協(xié)議，甚至路由協(xié)議的參數(shù)，適應(yīng)范圍過于狹窄。

2.3 基于網(wǎng)絡(luò)分層的算法

這類算法的共同點：在進行地址分配之前，對網(wǎng)絡(luò)的所有節(jié)點進行分簇；分簇以后，在簇內(nèi)通過DAD方法排除沖突地址或者選舉簇頭管理簇內(nèi)地址分配。為排除沖突地址的信息交互被局限在簇內(nèi)，從而減少了協(xié)議開銷，增強了可擴展性。在這類算法中，地址分配的協(xié)議開銷降低了，但因為移動自組網(wǎng)的拓撲結(jié)構(gòu)是動態(tài)變化的，維護網(wǎng)絡(luò)的分層結(jié)構(gòu)本身就是一筆不小的開銷，所以分簇的方法顯得尤為重要。IPv6Stateless[7]和SOAMAN[8]是這類算法的典型代表。

1）IPv6Stateless

該算法先把整個網(wǎng)絡(luò)進行分層，即把1組相距小于或等于rs跳的節(jié)點劃分為1個群，選舉鄰居節(jié)點數(shù)最多的節(jié)點作為群首節(jié)點，孤立節(jié)點可自立為群首。群內(nèi)所有節(jié)點共同構(gòu)成1個子網(wǎng)，群首節(jié)點負責(zé)選擇1個隨機的子網(wǎng)ID，并且在所有群首節(jié)點中進行DAD檢驗以保證該子網(wǎng)ID的唯一性。在子網(wǎng)ID確定下來以后，群首向群內(nèi)節(jié)點周期性地廣播RA （Router Advertisements）消息，消息中包含子網(wǎng)ID。新加入節(jié)點先隨機產(chǎn)生1個本地鏈路地址，并在群內(nèi)進行DAD檢測，如果沒有檢測到?jīng)_突，則將該本地鏈路地址和接收到的RA中的子網(wǎng)ID合成節(jié)點地址；否則重新選取地址，并重復(fù)上述過程。

該算法實行了分層的網(wǎng)絡(luò)結(jié)構(gòu)，將本地鏈路地址的DAD檢測限制在群內(nèi)，而子網(wǎng)ID的DAD檢測限制在群首節(jié)點之間，降低了協(xié)議開銷。但隨著節(jié)點的移動，網(wǎng)絡(luò)拓撲動態(tài)變化，維護分層結(jié)構(gòu)本身也是一筆不小的開銷，所以該算法不適合節(jié)點移動快、拓撲變化劇烈的網(wǎng)絡(luò)。

2）SOAMAN

該算法從所有節(jié)點中選舉1個群首節(jié)點管理整個網(wǎng)絡(luò)地址的分配，領(lǐng)導(dǎo)節(jié)點維護整個網(wǎng)絡(luò)的已分配地址表，新加入節(jié)點需向群首節(jié)點申請地址。當(dāng)有新節(jié)點加入網(wǎng)絡(luò)時，它首先隨機產(chǎn)生1個臨時地址，該地址只用于與鄰居節(jié)點（主要是代理申請地址的節(jié)點）的通信，不參與路由。然后，選擇1個鄰居節(jié)點作為申請地址的代理，該鄰居節(jié)點隨后向群首節(jié)點申請1個未分配的IP地址，并將其作為新加入節(jié)點的地址。

該算法新節(jié)點在加入網(wǎng)絡(luò)過程只需通過鄰居代理向群首節(jié)點申請地址，而不需要泛洪整個網(wǎng)絡(luò)，也不需要等待網(wǎng)絡(luò)中其他節(jié)點的確認消息，降低了協(xié)議開銷和配置延時。但是，整個網(wǎng)絡(luò)只劃分1個群，群首管理整個網(wǎng)絡(luò)的地址分配，并且需要周期性廣播信號以檢測網(wǎng)絡(luò)的分裂與合并，所以群首節(jié)點的負載較大，可能成為整個網(wǎng)絡(luò)的瓶頸，可擴展性不強。

2.4 其他算法

這些算法沒有統(tǒng)一的規(guī)律可循，它們通過某種特殊的方法或技巧為節(jié)點分配地址，可能帶來某一方面性能的提高，但也可能引起其他方面的一些問題。這里重點介紹 Prophet[9]和 MACBased[10]。

1）Prophet

該算法通過一個特殊的函數(shù)f（n）來生成地址，要求該函數(shù)產(chǎn)生2個相同隨機數(shù)的時間間隔足夠長。網(wǎng)絡(luò)中的第1個節(jié)點隨機選擇1個數(shù)作為自己的地址，第2個節(jié)點加入網(wǎng)絡(luò)時，第1個節(jié)點以自己的地址作為生成函數(shù)f（n）的種子生成1個數(shù)，作為第2節(jié)點的地址，以此類推。

該算法在地址分配過程中不需要通過泛洪排除重復(fù)地址，也不需要等待其他節(jié)點的確認消息，協(xié)議開銷較小，配置延時較小，可擴展性較好，但符合條件的f（n）不好找。其次，要求可分配的地址空間比實際使用的地址數(shù)大得多才行。再次，在節(jié)點頻繁加入離開網(wǎng)絡(luò)的情況下，還是可能產(chǎn)生重復(fù)地址的。

2）MACBased

該算法將IP地址和網(wǎng)卡的MAC地址對應(yīng)起來，用MAC地址的已知網(wǎng)絡(luò)前綴和后綴組成相應(yīng)的IP地址。該算法認為在全球范圍內(nèi)所有網(wǎng)卡的MAC地址是唯一的，不會有重復(fù)地址。但是，網(wǎng)卡的MAC地址可以通過對E2PROM編程更改。其次，可能出現(xiàn)不同網(wǎng)卡使用同一MAC地址的情況，所以MAC地址的唯一性得不到保證。再次，將IP地址與硬件地址對應(yīng)起來，知道了IP地址就知道了相應(yīng)的主機，個人隱私得不到保護。

3 性能比較

對于移動自組網(wǎng)的地址分配技術(shù)，一般從是否存在重復(fù)地址、協(xié)議開銷、配置延時、可擴展性、是否支持網(wǎng)絡(luò)分裂與合并這幾個方面來評價它們的性能。表2給出了4類地址分配技術(shù)典型算法的比較。

表2 典型地址分配算法的性能對比

4 小結(jié)

移動自組網(wǎng)的網(wǎng)絡(luò)拓撲結(jié)構(gòu)動態(tài)變化，在這樣的環(huán)境下，地址動態(tài)分配是一項具有挑戰(zhàn)性的工作。目前，不存在一般條件下各方面性能都較好的地址分配算法。應(yīng)考慮具體的應(yīng)用條件，選擇合適的算法。

影響移動自組網(wǎng)地址動態(tài)分配算法性能的主要因素是網(wǎng)絡(luò)拓撲的動態(tài)變化。如何感知和預(yù)測拓撲的變化以消除拓撲變化引起的各種問題，將成為未來改進算法性能的主要方向。

[1]NetworkWorkingGroup-RFC2131，Dynamichost configuration protocol[S].1997.

[2]NESARGI S，PRAKASH R.MANETconf:configuration of hosts in a mobile Ad Hoc network[C]//Proc.IEEE INFOCOM.New York，USA：[s.n.]，2002：1059-1068.

[3]MOSHIN M，PRAKASH R.IP address assignment in a mobile Ad Hoc network[C]//Proc.Military Communications Conference（MILCOM 2002）.California， USA：[s.n]，2002： 856-861.

[4]PRAKASH A，PATNAIK L M.An address assignment for the automatic configuration of mobile Ad Hoc networks[J].Personal and Ubiquitous Computing，2004，8（1）：47-54.

[5]PERKINS C E，MALINEN J T，WIKIKAWA R.IP address autocon figuration for Ad Hoc networks[S].2001.

[6]WENIGER K.PACMAN:passive autoconfiguration for mobile Ad Hoc networks[J].IEEE Journal on Selected Areas in Communications（JSAC），2005，23（3）：507-519.

[7]WENIGER K，ZITTERBART M.IPv6 autoconfiguration in large scale mobile Ad Hoc networks[C]//Proc.European Wireless 2002.Florence，Italy：[s.n.]，2002：142-148.

[8]TONER S，MAHONY D.Self-organising node address management in Ad-hoc networks[C]//Proc.No.8 IFIP-TC6 International Conference.Venice，Italy：[s.n.]，2003：476-483.

[9]ZHOU Hongbo，NI L M，MUTKA M W.Prophet address allocation for large scale MANETs[C]//Proc.IEEE Conference on Computer Communications（INFOCOM）.San Francisco，CA：[s.n.]，2003：423-434.

[10]IETF RFC 2462，IPv6 stateless address autoconfiguration[S].1998.