基于素?cái)?shù)地址的動(dòng)態(tài)無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議

劉鵬飛，劉 銘 ，劉赟卓，徐 楊（電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731）

基于素?cái)?shù)地址的動(dòng)態(tài)無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議

劉鵬飛，劉 銘 ，劉赟卓，徐 楊
（電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 611731）

針對(duì)分層式路由協(xié)議在建立整個(gè)網(wǎng)絡(luò)拓?fù)浜鬅o(wú)法動(dòng)態(tài)維護(hù)的缺點(diǎn)，本文修改了現(xiàn)有分層路由機(jī)制中節(jié)點(diǎn)地址的分配方法，提出素?cái)?shù)動(dòng)態(tài)路由協(xié)議。該協(xié)議利用素?cái)?shù)乘積分解的唯一性，使得節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置能被明確表示出來(lái)且可以動(dòng)態(tài)修改。通過(guò)仿真實(shí)驗(yàn)，對(duì)比常見(jiàn)的LEACH、SPIN和DD這3種路由協(xié)議，本文提出的D-HiPr路由協(xié)議在網(wǎng)絡(luò)生存時(shí)間、傳輸時(shí)延等方面表現(xiàn)更優(yōu)，很好地滿足異構(gòu)型無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用。

動(dòng)態(tài)路由；分層路由；素?cái)?shù)地址；無(wú)線傳感器網(wǎng)絡(luò)

基于上述研究現(xiàn)狀，本文設(shè)計(jì)并實(shí)現(xiàn)了基于素?cái)?shù)的動(dòng)態(tài)分層路由協(xié)議（dynamical hierarchical routing protocol with prime numbers，D-HiPr）。該協(xié)議基于素?cái)?shù)地址設(shè)計(jì)，實(shí)現(xiàn)分層路由協(xié)議，在低功耗無(wú)線傳感器網(wǎng)絡(luò)中建立動(dòng)態(tài)地址分配機(jī)制以支持節(jié)點(diǎn)的移動(dòng)，滿足網(wǎng)絡(luò)動(dòng)態(tài)化需求。

1 基于素?cái)?shù)地址的分層路由協(xié)議

1.1 素?cái)?shù)地址分配

D-HiPr路由協(xié)議是基于無(wú)線傳感器網(wǎng)絡(luò)中的分層路由協(xié)議，該協(xié)議將網(wǎng)絡(luò)形成樹(shù)形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。傳統(tǒng)的層次型路由協(xié)議支持的樹(shù)形結(jié)構(gòu)只適用于分布均勻的網(wǎng)絡(luò)，同時(shí)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的動(dòng)態(tài)性支持不完善。本文所介紹的素?cái)?shù)動(dòng)態(tài)分層路由適用于非均勻分布的網(wǎng)路，并對(duì)于節(jié)點(diǎn)的移動(dòng)性能夠更好地進(jìn)行支持。

圖1 素?cái)?shù)地址分配實(shí)例

基于素?cái)?shù)地址分配協(xié)議為每個(gè)節(jié)點(diǎn)分配一個(gè)16位的素?cái)?shù)地址Ap，作為其16位短地址，該地址在節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)由網(wǎng)關(guān)為節(jié)點(diǎn)分配。由于基于素?cái)?shù)地址分配協(xié)議沒(méi)有路由表協(xié)議，因此，為了標(biāo)識(shí)到各節(jié)點(diǎn)的路徑，還需要將從網(wǎng)關(guān)開(kāi)始到該節(jié)點(diǎn)的這條鏈路上的所有節(jié)點(diǎn)的16位素?cái)?shù)短地址相乘，以形成各節(jié)點(diǎn)的位置標(biāo)識(shí)LID［9］（location identifier）。當(dāng)一個(gè)節(jié)點(diǎn)連接到一個(gè)網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)除了得到一個(gè)網(wǎng)關(guān)分配的素?cái)?shù)地址外，還得到一個(gè)父節(jié)點(diǎn)的位置標(biāo)識(shí)Qp，節(jié)點(diǎn)將自己的16位素?cái)?shù)短地址與父節(jié)點(diǎn)的位置標(biāo)識(shí)相乘，就形成了自己的位置標(biāo)識(shí)Qc，Qc=Ap×Qp。位置標(biāo)識(shí)表示從網(wǎng)關(guān)節(jié)點(diǎn)到現(xiàn)在所在節(jié)點(diǎn)所經(jīng)過(guò)的路徑，例如所經(jīng)過(guò)的路徑包括節(jié)點(diǎn)的素?cái)?shù)地址為A1，A2，…，Ac，則Qc=A1×A2×…×Ac。利用以上兩種數(shù)據(jù)，就可以確定數(shù)據(jù)需要經(jīng)過(guò)的鏈路狀況，從而實(shí)現(xiàn)路由功能。例如，在圖1中，16位短地址為17的節(jié)點(diǎn)的LID為663=1×3×13×17。需要說(shuō)明的是，雖然數(shù)字1不是素?cái)?shù)，但對(duì)于一個(gè)多節(jié)點(diǎn)的傳感器系統(tǒng)而言，起始根節(jié)點(diǎn)以1作為標(biāo)識(shí)將直接簡(jiǎn)化實(shí)際地址分配過(guò)程的計(jì)算強(qiáng)度與復(fù)雜度且更容易辨識(shí)。

1.2 基于素?cái)?shù)的動(dòng)態(tài)網(wǎng)絡(luò)組網(wǎng)

在素?cái)?shù)動(dòng)態(tài)分層路由協(xié)議中，為了避免地址重復(fù)，所有的16位短地址都由網(wǎng)關(guān)進(jìn)行分配。節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)先使用無(wú)線網(wǎng)絡(luò)中的鄰居發(fā)現(xiàn)協(xié)議［10］，將所有一跳范圍內(nèi)的節(jié)點(diǎn)都作為鄰居節(jié)點(diǎn)儲(chǔ)存到鄰居列表里，接著選擇鏈路狀況最好的路由節(jié)點(diǎn)作為父節(jié)點(diǎn)。在本文所介紹的組網(wǎng)方式中，當(dāng)節(jié)點(diǎn)需要加入網(wǎng)絡(luò)時(shí)，首先發(fā)送路由請(qǐng)求報(bào)文（router solicitation，RS），而不是等待路由節(jié)點(diǎn)發(fā)送路由公告報(bào)文（router advertisement，RA），這是考慮到無(wú)線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)加入的不確定性，采用定期的路由公告發(fā)送不利于能量節(jié)約。其組網(wǎng)的過(guò)程中具體算法如下。

算法1：基于素?cái)?shù)地址的組網(wǎng)算法

基于素?cái)?shù)地址的組網(wǎng)算法如算法1所示，在該算法中，節(jié)點(diǎn)遞歸地加入到網(wǎng)絡(luò)中。首先，待加入網(wǎng)絡(luò)節(jié)點(diǎn)根據(jù)其自身包括剩余能量、通信帶寬等數(shù)據(jù)定義自身能力值（第2行），之后待加入網(wǎng)絡(luò)節(jié)點(diǎn)獲取其鄰居信息，并根據(jù)獲得的鄰居能力值將鄰居進(jìn)行由大到小的排序（第3、4行），并從排序好的鄰居列表中選擇第一個(gè)能力值大于待加入網(wǎng)絡(luò)節(jié)點(diǎn)的父節(jié)點(diǎn)，而且其子節(jié)點(diǎn)數(shù)未超過(guò)設(shè)定最大值。選擇好父節(jié)點(diǎn)之后，待加入網(wǎng)絡(luò)節(jié)點(diǎn)向其發(fā)送組網(wǎng)申請(qǐng)，并最終獲得其素?cái)?shù)地址和LID（第5～9行），組網(wǎng)過(guò)程繼續(xù)，直到所有節(jié)點(diǎn)均加入網(wǎng)絡(luò)。

節(jié)點(diǎn)加入網(wǎng)絡(luò)后，通過(guò)定期簡(jiǎn)單的“Hello”信息交換機(jī)制檢測(cè)鄰居節(jié)點(diǎn)是否可達(dá)。如果節(jié)點(diǎn)檢測(cè)到鄰居發(fā)生了變化，則會(huì)做出判斷，如果是父節(jié)點(diǎn)發(fā)生了變化（例如節(jié)點(diǎn)移動(dòng)到另一個(gè)地方），則需要重新在鄰居節(jié)點(diǎn)中選擇一個(gè)可以作為路由器的父節(jié)點(diǎn)，同時(shí)改變自己的位置標(biāo)識(shí)。如果父節(jié)點(diǎn)發(fā)現(xiàn)子節(jié)點(diǎn)發(fā)生變化，則將子節(jié)點(diǎn)刪除，因?yàn)檫@樣的變化極有可能是子節(jié)點(diǎn)離開(kāi)。必須注意的是，子節(jié)點(diǎn)必須隨時(shí)注意父節(jié)點(diǎn)是否發(fā)生變化，如果父節(jié)點(diǎn)發(fā)生變化，則必須同步改進(jìn)自己的位置標(biāo)識(shí)。

2 基于素?cái)?shù)地址的動(dòng)態(tài)路由

當(dāng)節(jié)點(diǎn)得到自己的素?cái)?shù)地址與位置標(biāo)識(shí)LID后，必須向網(wǎng)關(guān)發(fā)送位置標(biāo)識(shí)，網(wǎng)關(guān)獲取所有節(jié)點(diǎn)的位置標(biāo)識(shí)后，才能進(jìn)行路由。圖2展示了數(shù)據(jù)包的路由過(guò)程，其中，數(shù)據(jù)包所在的當(dāng)前節(jié)點(diǎn)為Node C，該節(jié)點(diǎn)的位置標(biāo)識(shí)為Qc，當(dāng)前節(jié)點(diǎn)所連接的父節(jié)點(diǎn)是Node P，位置標(biāo)識(shí)為Qp。數(shù)據(jù)包接受目的節(jié)點(diǎn)Node D，位置標(biāo)識(shí)為Qd。當(dāng)前節(jié)點(diǎn)下面還連接的子節(jié)點(diǎn)為Node Ki，位置標(biāo)識(shí)為Qkr。路由算法如下：

算法2：D-HiPr路由算法

在路由過(guò)程中，首先，在進(jìn)行路由之前當(dāng)前節(jié)點(diǎn)必須檢測(cè)父節(jié)點(diǎn)和子節(jié)點(diǎn)是否有效，即通過(guò)Hello Message機(jī)制檢查父節(jié)點(diǎn)和子節(jié)點(diǎn)是否在鏈路上，如果父節(jié)點(diǎn)不在鏈路上必須重新搜索父節(jié)點(diǎn)，并改變自己的位置標(biāo)識(shí)Qc；如果子節(jié)點(diǎn)不在鏈路上則直接將其從鄰居表中刪除。在檢查完父節(jié)點(diǎn)和子節(jié)點(diǎn)的有效性之后，將目的節(jié)點(diǎn)的位置標(biāo)識(shí)Qd與自身位置標(biāo)識(shí)Qc進(jìn)行比較（第2行），若差值大于0則將數(shù)據(jù)包需要傳遞給其子節(jié)點(diǎn)。首先將每個(gè)子節(jié)點(diǎn)的位置標(biāo)識(shí)Qkr與Qd相除（第3～5行），如果能整除就表示目的節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的子孫節(jié)點(diǎn)，則將數(shù)據(jù)包傳遞到相應(yīng)的子節(jié)點(diǎn)處（第6、7行）。如果其子節(jié)點(diǎn)位置標(biāo)識(shí)均不能被目的節(jié)點(diǎn)位置標(biāo)識(shí)整除，說(shuō)明目的節(jié)點(diǎn)不是當(dāng)前節(jié)點(diǎn)的子孫節(jié)點(diǎn)，則丟棄數(shù)據(jù)包（第8、9行）；若Qd與Qc的差值等于0則表示數(shù)據(jù)包就是發(fā)送給該節(jié)點(diǎn)的（第12、13行）；若Qd與Qc的差值小于0則表示目的節(jié)點(diǎn)不可能處于當(dāng)前節(jié)點(diǎn)子孫節(jié)點(diǎn)處，則將數(shù)據(jù)包傳遞給其父節(jié)點(diǎn)（第14、15行）；數(shù)據(jù)包在傳遞之后，新接收到數(shù)據(jù)包的節(jié)點(diǎn)對(duì)其進(jìn)行同樣的判斷，直到數(shù)據(jù)包傳到目的地，完成路由過(guò)程。

圖2 數(shù)據(jù)包傳遞過(guò)程

3 網(wǎng)絡(luò)動(dòng)態(tài)性支持與維護(hù)

無(wú)線傳感器網(wǎng)絡(luò)由于其節(jié)點(diǎn)個(gè)體的移動(dòng)性和分布式性質(zhì)，因此網(wǎng)絡(luò)具有很高的動(dòng)態(tài)性。又由于素?cái)?shù)動(dòng)態(tài)路由協(xié)議將網(wǎng)絡(luò)劃分成為一個(gè)樹(shù)形的拓?fù)浣Y(jié)構(gòu)，節(jié)點(diǎn)的移動(dòng)性會(huì)產(chǎn)生端節(jié)點(diǎn)移動(dòng)和網(wǎng)絡(luò)骨干節(jié)點(diǎn)移動(dòng)的不同情況，而素?cái)?shù)動(dòng)態(tài)路由協(xié)議對(duì)于端節(jié)點(diǎn)和骨干節(jié)點(diǎn)發(fā)生移動(dòng)的處理方式各有不同。

3.1 網(wǎng)絡(luò)端節(jié)點(diǎn)移動(dòng)響應(yīng)

當(dāng)網(wǎng)絡(luò)中的端節(jié)點(diǎn)的位置發(fā)生變化時(shí)，其地址的分配可看作是一個(gè)新節(jié)點(diǎn)加入網(wǎng)絡(luò)的過(guò)程，而與傳統(tǒng)動(dòng)態(tài)路由協(xié)議不同的是，移動(dòng)的節(jié)點(diǎn)依然會(huì)保留自身已被分配的素?cái)?shù)地址，在其重新組網(wǎng)時(shí)無(wú)需再向網(wǎng)關(guān)申請(qǐng)新的素?cái)?shù)地址，而只需尋找到其新父節(jié)點(diǎn)后計(jì)算出自身的新LID并將其發(fā)送到網(wǎng)關(guān)記錄。

如圖3中所例，傳感器網(wǎng)絡(luò)中61號(hào)節(jié)點(diǎn)從虛線位置移動(dòng)到箭頭所指位置后，通過(guò)基本的鄰居發(fā)現(xiàn)機(jī)制尋找能力值最優(yōu)鄰居節(jié)點(diǎn)作為其父節(jié)點(diǎn)；在重新加入網(wǎng)絡(luò)后，該節(jié)點(diǎn)素?cái)?shù)地址仍為61不變，僅將其LID由662765變?yōu)?05并發(fā)送到網(wǎng)關(guān)保持通信。

圖3 素?cái)?shù)地址動(dòng)態(tài)路由協(xié)議動(dòng)態(tài)支持舉例

3.2 網(wǎng)絡(luò)骨干節(jié)點(diǎn)失效響應(yīng)

無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)由于能量耗盡、硬件故障以及不可預(yù)知的移動(dòng)都會(huì)導(dǎo)致網(wǎng)絡(luò)及數(shù)據(jù)路由出現(xiàn)錯(cuò)誤，而其中骨干節(jié)點(diǎn)的失效直接使得節(jié)點(diǎn)間的通訊距離增大，增加傳輸能耗，甚至破壞網(wǎng)絡(luò)連通性。因此，針對(duì)骨干節(jié)點(diǎn)失效帶來(lái)的網(wǎng)絡(luò)連通問(wèn)題，需要單獨(dú)考慮。在一個(gè)骨干節(jié)點(diǎn)失效后，失效骨干節(jié)點(diǎn)的每個(gè)子節(jié)點(diǎn)都重新加入一次網(wǎng)絡(luò)的話，這就使得網(wǎng)絡(luò)效能的開(kāi)銷直接增大。

算法3：基于素?cái)?shù)路由的網(wǎng)絡(luò)重組算法

基于素?cái)?shù)動(dòng)態(tài)路由協(xié)議設(shè)計(jì)了一個(gè)網(wǎng)絡(luò)重組機(jī)制，如算法3所示。首先，失效父節(jié)點(diǎn)的子節(jié)點(diǎn)都形成后裔樹(shù)，而與失效父節(jié)點(diǎn)直接相連的每個(gè)子節(jié)點(diǎn)都為一棵后裔樹(shù)的根節(jié)點(diǎn)，每棵后裔樹(shù)的根節(jié)點(diǎn)都從鄰居中掃描可用的父節(jié)點(diǎn)，并在保持后裔樹(shù)成員節(jié)點(diǎn)連接的情況下，選擇最優(yōu)的進(jìn)行連接，每個(gè)后裔節(jié)點(diǎn)無(wú)需再發(fā)送入網(wǎng)申請(qǐng)，而直接可以從其父節(jié)點(diǎn)處獲得新的LID，之后向網(wǎng)關(guān)發(fā)送所有的LID更改。

4 實(shí)驗(yàn)結(jié)果與分析

為了更直觀地展現(xiàn)素?cái)?shù)動(dòng)態(tài)路由協(xié)議在無(wú)線傳感器網(wǎng)絡(luò)中的可行性及其路由效果，使用NS2作為實(shí)驗(yàn)仿真平臺(tái)，設(shè)計(jì)了相關(guān)仿真實(shí)驗(yàn)。

考慮傳統(tǒng)802.15.4/ZigBee無(wú)線傳感器節(jié)點(diǎn)特性，選擇連續(xù)流速度自適應(yīng)模型（continuous flow with rate adaption，CFRA）作為網(wǎng)絡(luò)傳輸基礎(chǔ)模式。該模式中數(shù)據(jù)包以穩(wěn)定且連續(xù)的形式傳輸，傳輸速率可從預(yù)設(shè)定中選取，因此節(jié)點(diǎn)能耗可通過(guò)網(wǎng)絡(luò)中的數(shù)據(jù)流量進(jìn)行統(tǒng)計(jì)和調(diào)節(jié)。整個(gè)傳感器網(wǎng)絡(luò)的通信能耗即網(wǎng)絡(luò)中所有節(jié)點(diǎn)在通信階段所消耗能量的總和。假設(shè)傳感器接收和發(fā)送的能耗相同［11］，則傳感器節(jié)點(diǎn)每收到一個(gè)數(shù)據(jù)包的能耗可設(shè)定為：

式中，k為數(shù)據(jù)包長(zhǎng)度；ecos為傳輸單位比特能耗。傳感器節(jié)點(diǎn)每傳遞一個(gè)數(shù)據(jù)包的能耗可設(shè)定為：

式中，dis表示傳輸距離；a表示節(jié)點(diǎn)硬件能耗。因此可以得出傳感器節(jié)點(diǎn)進(jìn)行中繼傳輸?shù)哪芎臑椋?/p>

基于上述多傳感器網(wǎng)絡(luò)傳輸能耗模型，針對(duì)不同協(xié)議和網(wǎng)絡(luò)規(guī)模設(shè)計(jì)相應(yīng)實(shí)驗(yàn)，具體參數(shù)由相應(yīng)實(shí)驗(yàn)場(chǎng)景設(shè)定。

4.1 多協(xié)議能耗對(duì)比

為了驗(yàn)證本文設(shè)計(jì)的素?cái)?shù)動(dòng)態(tài)路由協(xié)議降低網(wǎng)絡(luò)能耗的實(shí)際應(yīng)用效果，本文對(duì)比了其與傳統(tǒng)LEACH、SPIN以及定向擴(kuò)散（directed diffusion，DD）協(xié)議的網(wǎng)絡(luò)生存時(shí)間。在本項(xiàng)實(shí)驗(yàn)中，網(wǎng)絡(luò)設(shè)定為10×10的規(guī)則柵格布局，所有節(jié)點(diǎn)都具有相同的初始能量值，且傳感器傳輸一個(gè)數(shù)據(jù)包消耗相同的能量值，即每一輪所有節(jié)點(diǎn)均發(fā)送/接受數(shù)據(jù)包，同時(shí)每個(gè)節(jié)點(diǎn)的能量值隨發(fā)送/接受的過(guò)程不斷減少，直到最后能量耗盡。實(shí)驗(yàn)重復(fù)6 000次。

實(shí)驗(yàn)結(jié)果如圖4所示，其中縱坐標(biāo)表示活躍節(jié)點(diǎn)數(shù)，橫坐標(biāo)便是數(shù)據(jù)包數(shù)次數(shù)，方格線代表本研究設(shè)計(jì)的素?cái)?shù)動(dòng)態(tài)路由協(xié)議。通過(guò)實(shí)驗(yàn)結(jié)果不難看出，LEACH協(xié)議在運(yùn)行過(guò)程中不斷地循環(huán)執(zhí)行簇的重構(gòu)過(guò)程，同時(shí)協(xié)議缺乏有效機(jī)制實(shí)現(xiàn)簇頭節(jié)點(diǎn)均勻分布。因此，隨機(jī)選取使得簇頭節(jié)點(diǎn)會(huì)以一定概率集中在某一區(qū)域，這樣就會(huì)使得一些節(jié)點(diǎn)的周圍沒(méi)有任何簇頭節(jié)點(diǎn)，從而導(dǎo)致網(wǎng)絡(luò)能耗分布不均勻，一旦簇頭節(jié)點(diǎn)死亡，會(huì)快速造成網(wǎng)絡(luò)中的能量黑洞區(qū)域。

SPIN路由協(xié)議的源節(jié)點(diǎn)在傳輸新數(shù)據(jù)時(shí)，直接向鄰居節(jié)點(diǎn)廣播消息。沒(méi)有考慮當(dāng)有多個(gè)鄰居節(jié)點(diǎn)都在能量充足，都愿擔(dān)任數(shù)據(jù)中轉(zhuǎn)站的角色時(shí)，將出現(xiàn)“盲目轉(zhuǎn)發(fā)”問(wèn)題；同時(shí)由于網(wǎng)絡(luò)節(jié)點(diǎn)能量低于設(shè)定閾值或目的地超出當(dāng)前轉(zhuǎn)發(fā)范圍等原因，也會(huì)導(dǎo)致部分“數(shù)據(jù)不可達(dá)”的問(wèn)題；而DD路由協(xié)議在周期性的flooding機(jī)制影響下，其能量和時(shí)間開(kāi)銷都比較大，同時(shí)節(jié)點(diǎn)需要維護(hù)一個(gè)興趣消息列表，代價(jià)較大。

圖4 不同網(wǎng)絡(luò)協(xié)議的網(wǎng)絡(luò)生存時(shí)間對(duì)比

因此，通過(guò)對(duì)比實(shí)驗(yàn)可以看出，對(duì)于無(wú)線傳感器網(wǎng)絡(luò)中比較常見(jiàn)的LEACH、SPIN和DD三種路由協(xié)議來(lái)說(shuō)，本研究設(shè)計(jì)的基于素?cái)?shù)的動(dòng)態(tài)路由協(xié)議，實(shí)驗(yàn)中隨著數(shù)據(jù)傳輸應(yīng)用的持續(xù)，傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的生存時(shí)間遠(yuǎn)大于傳統(tǒng)的路由協(xié)議。

4.2 不同網(wǎng)絡(luò)規(guī)模下傳輸延遲對(duì)比

在本實(shí)驗(yàn)中，主要對(duì)比在不同的網(wǎng)絡(luò)規(guī)模下，傳統(tǒng)的分層路由協(xié)議LEACH與素?cái)?shù)動(dòng)態(tài)路由的網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)延對(duì)比，實(shí)驗(yàn)結(jié)果如圖5所示。統(tǒng)計(jì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)繁忙度從0～100％的有效實(shí)驗(yàn)過(guò)程，實(shí)驗(yàn)對(duì)比了在不同網(wǎng)絡(luò)規(guī)模，即網(wǎng)絡(luò)中具有100個(gè)、400個(gè)、700個(gè)和1 000個(gè)節(jié)點(diǎn)時(shí)傳統(tǒng)的LEACH協(xié)議與素?cái)?shù)動(dòng)態(tài)路由協(xié)議的數(shù)據(jù)傳輸時(shí)延對(duì)比。

圖5 不同網(wǎng)絡(luò)規(guī)模的傳輸時(shí)延對(duì)比

從如圖5所示的實(shí)驗(yàn)結(jié)果中可以看出，隨著網(wǎng)絡(luò)中數(shù)據(jù)流量的逐漸增加，任意網(wǎng)絡(luò)規(guī)模中的繁忙節(jié)點(diǎn)數(shù)逐漸增加，相應(yīng)的網(wǎng)絡(luò)傳輸延遲也在不斷增加。其中LEACH協(xié)議的基本思想在于以循環(huán)的方式隨機(jī)選擇簇頭節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，LEACH協(xié)議在運(yùn)行過(guò)程中不斷地循環(huán)執(zhí)行簇的重構(gòu)過(guò)程，因此，傳感器網(wǎng)絡(luò)在使用LEACH協(xié)議時(shí)，都需要有一個(gè)簇的建立時(shí)間，因此LEACH協(xié)議的網(wǎng)絡(luò)延遲一直較高。

本文設(shè)計(jì)的基于素?cái)?shù)的動(dòng)態(tài)路由協(xié)議實(shí)現(xiàn)了一種較直接的尋路方法，使得無(wú)線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)包能夠更快地到達(dá)目的節(jié)點(diǎn)，快捷而簡(jiǎn)單的計(jì)算方式大大降低了轉(zhuǎn)發(fā)節(jié)點(diǎn)的能耗。同時(shí)，有效改善了網(wǎng)絡(luò)中因簇頭或網(wǎng)關(guān)節(jié)點(diǎn)因頻繁轉(zhuǎn)發(fā)而帶來(lái)的高延遲和網(wǎng)絡(luò)擁塞。考慮實(shí)際應(yīng)用中，通常并非所有的數(shù)據(jù)包都需要發(fā)送到網(wǎng)關(guān)，尤其是結(jié)合物聯(lián)網(wǎng)應(yīng)用需求，多終端的動(dòng)態(tài)接入對(duì)網(wǎng)絡(luò)內(nèi)數(shù)據(jù)的查詢或調(diào)用，采用傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)，網(wǎng)關(guān)節(jié)點(diǎn)負(fù)載往往過(guò)重。而素?cái)?shù)動(dòng)態(tài)分層路由協(xié)議對(duì)于網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)，只要知道目的地的乘積地址，即可實(shí)現(xiàn)直接路徑通信，從而有效減少網(wǎng)關(guān)處帶寬的壓力。

而隨著網(wǎng)絡(luò)規(guī)模的變大，整個(gè)系統(tǒng)內(nèi)節(jié)點(diǎn)處理時(shí)延和傳輸時(shí)延都有所上升，同時(shí)網(wǎng)內(nèi)繁忙節(jié)點(diǎn)數(shù)量的增加也加劇了網(wǎng)絡(luò)傳輸時(shí)延。通過(guò)不同規(guī)模的實(shí)驗(yàn)可以發(fā)現(xiàn)，基于素?cái)?shù)的動(dòng)態(tài)路由協(xié)議的網(wǎng)絡(luò)傳輸時(shí)延遠(yuǎn)小于傳統(tǒng)的分層路由協(xié)議LEACH。

5 結(jié)論

本文提出并構(gòu)建了基于素?cái)?shù)的動(dòng)態(tài)分層路由協(xié)議，該協(xié)議適用于低功耗IEEE 802.15.4無(wú)線傳感器網(wǎng)絡(luò)，不需要路由表，只需要維護(hù)鄰居緩存的內(nèi)容即可完成網(wǎng)內(nèi)路由。基于素?cái)?shù)短地址與其他節(jié)點(diǎn)的短地址乘積得出的位置標(biāo)識(shí)LID，即確定數(shù)據(jù)包發(fā)送的方向，進(jìn)而實(shí)現(xiàn)路由功能。該協(xié)議利用素?cái)?shù)乘積分解的唯一性原理，使得節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置能被明確表示出來(lái)，且可以動(dòng)態(tài)修改。最后基于網(wǎng)絡(luò)仿真平臺(tái)，給出了對(duì)比試驗(yàn)，分別在相同網(wǎng)絡(luò)規(guī)模下網(wǎng)絡(luò)生存時(shí)間、不同網(wǎng)絡(luò)規(guī)模下傳輸延遲方面，將提出的基于素?cái)?shù)的路由協(xié)議與傳統(tǒng)路由協(xié)議進(jìn)行了對(duì)比，試驗(yàn)結(jié)果也充分說(shuō)明了基于素?cái)?shù)路由的有效性和可行性。

最后，對(duì)本文工作有如下討論。首先，本論文的研究?jī)H基于網(wǎng)絡(luò)仿真平臺(tái)對(duì)提出協(xié)議進(jìn)行了驗(yàn)證，還沒(méi)有在實(shí)際物理網(wǎng)絡(luò)中進(jìn)行測(cè)試，得出試驗(yàn)數(shù)據(jù)與實(shí)際應(yīng)還有差距，整個(gè)協(xié)議的完整度和功能還有待進(jìn)一步提升；其次，協(xié)議的安全性是動(dòng)態(tài)路由協(xié)議的一個(gè)核心問(wèn)題。本文的設(shè)計(jì)建立在適用于家庭或醫(yī)院等低功耗無(wú)線傳感器網(wǎng)絡(luò)為主要場(chǎng)景下。在這一場(chǎng)景下，對(duì)于安全性具有一定局限性并基于兩點(diǎn)假設(shè)：1）無(wú)線傳感器網(wǎng)絡(luò)通過(guò)特定網(wǎng)關(guān)接入互聯(lián)網(wǎng)，網(wǎng)關(guān)同時(shí)作為防火墻防止互聯(lián)網(wǎng)惡意程序訪問(wèn)網(wǎng)關(guān)內(nèi)的傳感器節(jié)點(diǎn)，并由網(wǎng)關(guān)負(fù)責(zé)數(shù)據(jù)安全性和避免被惡意篡改。2）由于目前考慮的無(wú)線傳感器網(wǎng)絡(luò)規(guī)模不大，并在應(yīng)用場(chǎng)景中可以在網(wǎng)絡(luò)部署階段對(duì)傳感器節(jié)點(diǎn)進(jìn)行安全性接入認(rèn)證，因此傳感器網(wǎng)絡(luò)內(nèi)部安全性比較容易保證。然而當(dāng)設(shè)計(jì)的基于素?cái)?shù)的動(dòng)態(tài)路由協(xié)議應(yīng)用于具有較大規(guī)模或存在惡意數(shù)據(jù)接入的應(yīng)用場(chǎng)景下時(shí)（例如在軍事應(yīng)用中），其安全性設(shè)計(jì)仍具有很大的挑戰(zhàn)，同時(shí)也是未來(lái)在素?cái)?shù)路由協(xié)議機(jī)制研究上的一個(gè)重要工作。

［1］WU S，XU Y，WEN J，et al.Hierarchical routing and path recovery algorithm in home 6LoWPAN networks［C］//IEEE 14th International Conference on Communication Technology（ICCT）.Chengdu，China：IEEE，2012：51-55.

［2］ANGELOPOULOS G，PAIDIMARRI A，CHANDRAKASAN A P，et al.Experimental study of the interplay of channel and network coding in low power sensor applications［C］//IEEE International Conference on Communications（ICC）.［S.l.］：IEEE，2013：5126-5130.

［3］KUMAR G V，REDDYR Y V，NAGENDRA M.Current research work on routing protocols for MANET：a literature survey［J］.International Journal on Computer Science ＆Engineering，2010，2（3）：706-713.

［4］LIU M，XU Y，WU S，et al.Design and optimization of hierarchical routing protocol for 6LoWPAN［J］.International Journal of Distributed Sensor Networks，2015，15：150-160.

［5］VAIDYA N H.Weak duplicate address detection in mobile ad hoc networks［C］//Proceedings of the 3rd ACMInternational Symposium on Mobile Ad Hoc Networking ＆Computing.Lausanne，Switzerland：［s.n.］，2002：206-216.

［6］GAMMAR S M，AMINE E，KAMOUN F.Distributed address auto configuration protocol for Manet networks［J］.Telecommunication Systems，2010，44（1-2）：39-48.

［7］CHOWDHURY A H，IKRAM M，CHA H S，et al.Route-over vs Mesh-under routing in 6LoWPAN［C］//Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing：Connecting the World Wirelessly.Leipzig，Germany：［s.n.］，2009：1208-1212.

［8］TALREJA R，JETHANI V.A vote based system to detect misbehaving nodes in MANETs［C］//Advance Computing Conference（IACC）.［S.l.］：IEEE，2014：391-394.

［9］GUAN J，YOU I，XU C，et al.Survey on route optimization schemes for proxy mobile IPv6［C］//2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing（IMIS）.［S.l.］：IEEE，2012：541-546.

［10］GK EE，CK NG，NOORDIN N K，et al.Path recovery mechanism in 6LOWPANs routing［C］//2010 International Conference on Computer and Communication Engineering.Kuala Lumpur：IEEE，2010：1-5.

［11］NOH D K，ABDELZAHER T F.Efficient flow-control algorithm cooperating with energy allocation scheme for solar-powered WSNs［J］.Wireless Communications and Mobile Computing，2012，12（5）：379-392.

編輯 蔣 曉

The Dynamic Wireless Sensor Network Routing Protocol Based on Prime-Numbered Addresses

LIU Peng-fei，LIU Ming，LIU Yun-zhuo，and XU Yang
（School of Computer Science and Engineering，University of Electronic Science and Technology of China Chengdu 611731）

One key disadvantage identified with the hierarchical routing protocol is the lack of capacity to dynamically maintain the network topology after the establishment of an entire network topology.In this paper，a new routing protocol is proposed for short address allocation，which named dynamical hierarchical routing protocol with prime numbers.This protocol utilizes a unique decomposition product of prime numbers，and makes the networked position of the node can be represented explicitly and can be modified dynamically.The analysis of simulation results proved that，the D-HiPr routing protocol takes more advantage than LEACH，SPIN and DD routing protocols in the fields of the network survival time and the transmission delay，in addition，the D-HiPr routing protocol well meet the heterogeneous wireless sensor network applications.

dynamical routing；hierarchical routing algorithm；prime numbered address；wireless sensor network基于IEEE802.15.4標(biāo)準(zhǔn)的低功耗無(wú)線傳感器網(wǎng)絡(luò)［1-2］是近年來(lái)一個(gè)熱門研究領(lǐng)域，而其中設(shè)計(jì)基于低功耗網(wǎng)絡(luò)設(shè)備的快速路由機(jī)制更是一個(gè)研究熱點(diǎn)。文獻(xiàn)［3］對(duì)傳統(tǒng)的MANET（mobile Ad-hoc networks）應(yīng)用中動(dòng)態(tài)地址分配算法和路由算法作了較全面的概述，其中一個(gè)特點(diǎn)就是，復(fù)雜的算法設(shè)計(jì)往往在節(jié)點(diǎn)過(guò)多或節(jié)點(diǎn)動(dòng)態(tài)移動(dòng)的情形下容易造成子節(jié)點(diǎn)地址的沖突或路由失效，算法執(zhí)行代價(jià)過(guò)高，如：重復(fù)地址檢測(cè)算法（duplicate address detection，DAD）［4］或者弱重復(fù)地址檢測(cè)算法（weakDAD）［5］雖然解決了地址分配的唯一性問(wèn)題，但算法設(shè)計(jì)相對(duì)復(fù)雜；AAA算法［6］為即將加入網(wǎng)絡(luò)的節(jié)點(diǎn)預(yù)先分配了一個(gè)地址區(qū)段，每個(gè)加入節(jié)點(diǎn)的地址都會(huì)從這個(gè)區(qū)段中進(jìn)行隨機(jī)選擇；MANETconf算法［7］假設(shè)每個(gè)節(jié)點(diǎn)都儲(chǔ)存著網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)可能需要的地址，當(dāng)新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)，從其鄰居節(jié)點(diǎn)就可以獲得需要的地址。但對(duì)于低功耗無(wú)線傳感器網(wǎng)絡(luò)來(lái)說(shuō)，這種硬件設(shè)計(jì)受限的網(wǎng)絡(luò)應(yīng)用限制是不適用的；文獻(xiàn)［8］提出基于小型系統(tǒng)的專用節(jié)點(diǎn)地址分配，然而對(duì)于無(wú)基站的低功耗無(wú)線傳感器網(wǎng)絡(luò)同樣不適用。

TP393

A

10.3969/j.issn.1001-0548.2015.05.020

2015-02-21；

2015-06-15

國(guó)家自然科學(xué)基金（61370151，61202211）；國(guó)家科技重大專項(xiàng)（2015ZX03003012）

劉鵬飛（1985-），男，博士，主要從事分布式人工智能、傳感器網(wǎng)絡(luò)及多智能體系統(tǒng)方面的研究.