[發(fā)明專利]一種小規(guī)模無線傳感器網(wǎng)絡(luò)的路由方法

在審

• 申請?zhí)枺?/td>: 201410705802.2
• 申請日: 2014-11-28
• 公開（公告）號: CN104486807A
• 公開（公告）日: 2015-04-01
• 發(fā)明（設(shè)計）人: 董燕;曾冰
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W40/10;H04W40/24
• 代理公司: 華中科技大學(xué)專利中心 42201
• 代理人: 曹葆青

1.一種小規(guī)模無線傳感器網(wǎng)絡(luò)的路由方法，包括傳遞全局信息步驟、發(fā)送數(shù)據(jù)包步驟、傳遞數(shù)據(jù)包步驟和更新剩余能量信息步驟，其特征在于：

(1)傳遞全局信息步驟：

首先，對網(wǎng)絡(luò)中包括匯聚節(jié)點在內(nèi)的各傳感器節(jié)點分別進行編號，作為它們各自唯一的標識；將匯聚節(jié)點設(shè)置成與各傳感器節(jié)點相同的發(fā)送功率，匯聚節(jié)點在網(wǎng)絡(luò)內(nèi)向鄰居節(jié)點廣播路由消息，其中包括各傳感器節(jié)點到匯聚節(jié)點的跳數(shù)；各鄰居節(jié)點收到路由消息后，將其中自身到匯聚節(jié)點的跳數(shù)加1后，再向自身的鄰居節(jié)點廣播更新的路由消息；這樣，每個傳感器節(jié)點都能知道自身到匯聚節(jié)點的跳數(shù)、自身的鄰居節(jié)點、與鄰居節(jié)點的距離以及鄰居節(jié)點到匯聚節(jié)點的跳數(shù)；

然后，各傳感器節(jié)點將其與鄰居節(jié)點的距離、鄰居節(jié)點的編號、鄰居節(jié)點到匯聚節(jié)點的跳數(shù)以及自身現(xiàn)有能量和跳數(shù)發(fā)送到匯聚節(jié)點，匯聚節(jié)點將各傳感器節(jié)點的鄰居節(jié)點按照編號從小到大排序，形成各傳感器節(jié)點的鄰居節(jié)點集合；再由匯聚節(jié)點在網(wǎng)絡(luò)內(nèi)以廣播方式向每個傳感器節(jié)點傳遞全局信息；

所述全局信息包括各傳感器節(jié)點的鄰居節(jié)點集合、各傳感器節(jié)點與鄰居節(jié)點的距離、各傳感器節(jié)點的現(xiàn)有能量以及各傳感器節(jié)點到匯聚節(jié)點的跳數(shù)；

(2)發(fā)送數(shù)據(jù)包步驟：

當(dāng)某傳感器節(jié)點監(jiān)測到環(huán)境信息，先將其處理成為數(shù)據(jù)包，然后根據(jù)自身存儲的全局信息，計算自身到匯聚節(jié)點的最優(yōu)路徑，并將所述最優(yōu)路徑加入數(shù)據(jù)包；接著計算出最優(yōu)路徑中其它各傳感器節(jié)點轉(zhuǎn)發(fā)所述數(shù)據(jù)包需要消耗的能量和剩余能量，并更新自身存儲的全局信息中在最優(yōu)路徑上的其它各傳感器節(jié)點的剩余能量；再將自身剩余能量加入所述數(shù)據(jù)包后，將數(shù)據(jù)包按照所述最優(yōu)路徑發(fā)送到下一傳感器節(jié)點；

(3)傳遞數(shù)據(jù)包步驟：

下一傳感器節(jié)點接收到所述數(shù)據(jù)包，將自身剩余能量加入到該數(shù)據(jù)包，按照數(shù)據(jù)包中的最優(yōu)路徑繼續(xù)將數(shù)據(jù)包發(fā)送給下一傳感器節(jié)點，如此繼續(xù)，直到數(shù)據(jù)包傳送到匯聚節(jié)點；

(4)更新剩余能量信息步驟：

匯聚節(jié)點收到所述數(shù)據(jù)包后，對數(shù)據(jù)包進行處理，將其中傳感器節(jié)點監(jiān)測到的環(huán)境信息通過因特網(wǎng)或者衛(wèi)星傳送給用戶；利用數(shù)據(jù)包中各傳感器節(jié)點的剩余能量信息更新存儲的全局信息，匯聚節(jié)點以一定周期向各傳感器節(jié)點廣播所有節(jié)點剩余能量信息。

2.如權(quán)利要求1所述的路由方法，其特征在于：

所述發(fā)送數(shù)據(jù)包步驟中，計算所述最優(yōu)路徑包括下述子步驟：

子步驟1、設(shè)置路徑庫PM的大小H、最小選擇概率C_min、最大選擇概率C_max以及評價次數(shù)N：

PM＝[X₁，X₂，…，X_r，…，X_H]^T，其中，X_r為第r條路徑，表示當(dāng)前傳感器節(jié)點到匯聚節(jié)點的路徑，r＝1、2、…、H，X_r＝{s，…，x_r,j，…，d}，式中，s為當(dāng)前傳感器節(jié)點，d為匯聚節(jié)點，x_r,j為第r條路徑中的第j個傳感器節(jié)點；

H＝3～12，0≤C_min≤C_max≤1，N＝200～800；

子步驟2、對路徑庫PM中每條路徑初始化，包括下述過程：

(2.1)將路徑長度變量j賦值1，將傳感器節(jié)點s設(shè)置為當(dāng)前初始化路徑的第j個傳感器節(jié)點；

(2.2)將j+1的值賦值給j，為當(dāng)前初始化路徑選擇第j個傳感器節(jié)點：

判斷當(dāng)前初始化路徑第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)是否存在未選擇過的傳感器節(jié)點，是則進行過程(2.3)，否則轉(zhuǎn)過程(2.1)；

(2.3)首先產(chǎn)生0到1之間的隨機數(shù)R，然后用R減去當(dāng)前初始化路徑中第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)未選擇過的編號最小傳感器節(jié)點的選擇概率，判斷其差值是否不大于0，是則進行過程(2.4)，否則轉(zhuǎn)過程(2.5)；

(2.4)將所述未選擇過的編號最小傳感器節(jié)點作為當(dāng)前初始化路徑的第j個傳感器節(jié)點，轉(zhuǎn)過程(2.6)；

(2.5)將所述差值繼續(xù)減去當(dāng)前初始化路徑中第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)未選擇過的編號次小傳感器節(jié)點的選擇概率，再判斷其結(jié)果是否不大于0，是則將所述未選擇過的編號次小傳感器節(jié)點作為當(dāng)前初始化路徑的第j個傳感器節(jié)點，否則如此繼續(xù)直到最后的差值不大于0，用當(dāng)前初始化路徑第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)最后涉及其選擇概率的傳感器節(jié)點作為當(dāng)前初始化路徑的第j個傳感器節(jié)點，轉(zhuǎn)過程(2.6)；

(2.6)判斷當(dāng)前初始化路徑的第j個傳感器節(jié)點是否為匯聚節(jié)點，是則生成一條初始路徑；否則轉(zhuǎn)過程(2.2)；

對路徑庫PM中每條路徑重復(fù)過程(2.1)～(2.6)，共生成H條初始路徑，完成PM的初始化；

子步驟3、計算路徑庫中各路徑的適應(yīng)度f(X_r)：

式中，E(X_r)為路徑X_r中的傳感器節(jié)點傳遞數(shù)據(jù)包所消耗的總能量，E(Xr)=2×(L-1)×Eeles×k+Eamp×k×Σi=1L-1di,i+12,]]>L為路徑長度，d_i,i+1是傳感器節(jié)點i和傳感器節(jié)點i+1之間的距離，傳感器節(jié)點中接收和傳送電路工作時所消耗的能量E_elec為50nJ/bit，傳感器節(jié)點中傳送放大器工作時所消耗的能量E_amp為0.1nJ/bit/m²；k為傳感器節(jié)點所傳送的數(shù)據(jù)包大小，單位為比特；E_Min為路徑X_r中剩余能量最少的傳感器節(jié)點的剩余能量，E_Avg為路徑X_r中所有傳感器節(jié)點的平均剩余能量；

子步驟4、設(shè)置評價次數(shù)變量t＝1；

子步驟5、設(shè)置路徑條數(shù)變量r＝1；

子步驟6、產(chǎn)生候選路徑X'，包括下述過程：

(6.1)將1賦值給路徑長度變量j，將當(dāng)前傳感器節(jié)點s設(shè)置為侯選路徑X'的第j個傳感器節(jié)點；

(6.2)將j+1的值賦值給j，判斷侯選路徑X'中第j－1個傳感器節(jié)點的鄰居節(jié)點范圍內(nèi)是否存在未曾選擇過的傳感器節(jié)點，是則進行過程(6.3)，否則轉(zhuǎn)過程(6.1)；

(6.3)為侯選路徑X'選擇第j個傳感器節(jié)點：

產(chǎn)生0到1之間的隨機數(shù)R，判斷是否R＜C，是則進行過程(6.4)，否則進行過程(6.7)；所述選擇概率C=Cmin×exp((t-1)×ln(Cmax/Cmin)N-1);]]>

(6.4)判斷路徑庫PM中是否存在具有第j個傳感器節(jié)點的路徑，是則進行過程(6.5)；否則進行過程(6.7)；

(6.5)判斷路徑庫中各條路徑的第j個傳感器節(jié)點中是否有在候選路徑的第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)，且未選擇過的傳感器節(jié)點，是則進行過程(6.6)，否則進行過程(6.7)；

(6.6)從各條具有第j個傳感器節(jié)點的路徑的第j個傳感器節(jié)點組成的集合內(nèi)隨機選擇一個在候選路徑的第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)，且未選擇過的傳感器節(jié)點作為候選路徑的第j個傳感器節(jié)點，進行過程(6.8)；

(6.7)從候選路徑中第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)隨機選擇一個未選擇過的傳感器節(jié)點作為候選路徑的第j個傳感器節(jié)點，進行過程(6.8)；

(6.8)判斷候選路徑中的第j個傳感器節(jié)點是否為匯聚節(jié)點，是則進行過程(6.9)，否則轉(zhuǎn)過程(6.2)；

(6.9)生成一條侯選路徑X'，按照子步驟3的計算式，計算侯選路徑的適應(yīng)度f(X')，判斷f(X')是否小于路徑庫中適應(yīng)度最大的路徑的適應(yīng)度，是則以侯選路徑X'替換掉路徑庫中適應(yīng)度最大的路徑，進行子步驟7；否則，對路徑庫不做任何改變，進行子步驟7；

子步驟7、將t+1的值賦予t，判斷是否t≤N，是則執(zhí)行子步驟8，否則執(zhí)行子步驟11；

子步驟8、從路徑庫的第r條路徑X_r中除源節(jié)點和匯聚節(jié)點外任選一傳感器節(jié)點x_j進行鄰域搜索，包括下述過程：

(8.1)選擇路徑X_r中除源節(jié)點和匯聚節(jié)點外的任一傳感器節(jié)點x_j，判斷傳感器節(jié)點x_j的上一跳傳感器節(jié)點x_j-1的鄰居節(jié)點集合和下一跳傳感器節(jié)點x_j+1的鄰居節(jié)點集合的交集內(nèi)是否有不在路徑X_r中的傳感器節(jié)點，是則進行過程(8.2)；否則對路徑X_r不做任何改變；

(8.2)在所述交集內(nèi)隨機選擇一個不在路徑X_r中的傳感器節(jié)點替換傳感器節(jié)點x_j，得到新路徑X'_r，根據(jù)子步驟3的計算式，計算新路徑X'_r的適應(yīng)度f(X'_r)，判斷是否f(X'_r)＜f(X_r)，是則以X'_r替換掉X_r，進行子步驟9；否則，對路徑X_r不做任何改變，進行子步驟9；

子步驟9、將t+1的值賦予t，判斷是否t≤N，是則執(zhí)行子步驟10，否則執(zhí)行子步驟11；

子步驟10、將r+1的值賦予r，判斷是否r≤H，是則執(zhí)行子步驟6，否則執(zhí)行子步驟5；

子步驟11、選擇路徑庫中適應(yīng)度最小的一條路徑作為最優(yōu)路徑。

3.如權(quán)利要求2所述的路由方法，其特征在于：

所述子步驟2的過程(2.3)或(2.5)中，當(dāng)前初始化路徑中第j－1個傳感器節(jié)點的鄰居節(jié)點集合內(nèi)未選擇過的編號最小或編號次小傳感器節(jié)點i的選擇概率P(j-1,i)：

P(j-1,i)=Σm∈aj-1hm-hi(N(aj-1)-1)×Σm∈aj-1hm;]]>

式中，a_j-1表示第j－1個傳感器節(jié)點的鄰居節(jié)點集合，N(a_j-1)為集合a_j-1的元素數(shù)量，h_i表示a_j-1中傳感器節(jié)點i的跳數(shù)，h_m表示a_j-1中傳感器節(jié)點m的跳數(shù)。