[發(fā)明專利]用于水下傳感網(wǎng)絡(luò)多目標(biāo)優(yōu)化機(jī)會(huì)路由的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201911185266.7
• 申請(qǐng)日: 2019-11-27
• 公開(kāi)（公告）號(hào): CN110933676B
• 公開(kāi)（公告）日: 2022-04-22
• 發(fā)明（設(shè)計(jì)）人: 覃琴;徐海濤;王鑫;田藝
• 申請(qǐng)（專利權(quán)）人: 桂林電子科技大學(xué)
• 主分類(lèi)號(hào): H04W12/06
• 分類(lèi)號(hào): H04W12/06;H04W24/02;H04W40/10;H04W84/18;H04B13/02
• 代理公司: 桂林市華杰專利商標(biāo)事務(wù)所有限責(zé)任公司 45112
• 代理人: 劉梅芳

1.用于水下傳感網(wǎng)絡(luò)多目標(biāo)優(yōu)化機(jī)會(huì)路由的方法，其特征在于，包括如下步驟：

1)定義多目標(biāo)優(yōu)化機(jī)會(huì)路由MOO-BA路由：在MOO-BA的路由分組類(lèi)型和消息格式中，任何數(shù)據(jù)包的數(shù)據(jù)包標(biāo)題包含兩個(gè)字段：發(fā)件人ID，數(shù)據(jù)包序列號(hào)，發(fā)件人ID是水下傳感器節(jié)點(diǎn)的標(biāo)識(shí)符；分組序列號(hào)是由水下傳感器節(jié)點(diǎn)分配給分組的唯一序列號(hào)，發(fā)件人ID與數(shù)據(jù)包序列號(hào)相結(jié)合有助于避免路由過(guò)程中的重復(fù)，路由信息包括能量和深度，能量是信標(biāo)節(jié)點(diǎn)的剩余能量，深度是當(dāng)前轉(zhuǎn)發(fā)器的深度信息，在信標(biāo)發(fā)送階段每個(gè)節(jié)點(diǎn)自動(dòng)更新；

路由信息包括五種類(lèi)型的請(qǐng)求，即邀請(qǐng)請(qǐng)求、邀請(qǐng)請(qǐng)求接受、邀請(qǐng)請(qǐng)求確認(rèn)、邀請(qǐng)請(qǐng)求拒絕、選擇另一個(gè)最佳轉(zhuǎn)發(fā)器，邀請(qǐng)請(qǐng)求IR是發(fā)送給符合條件的一跳鄰居的初始信標(biāo)消息，在接收到邀請(qǐng)請(qǐng)求后，在動(dòng)態(tài)壽命估計(jì)DLE之后發(fā)出邀請(qǐng)請(qǐng)求接受IRA，邀請(qǐng)請(qǐng)求確認(rèn)IRC是數(shù)據(jù)傳輸之前的最終消息，邀請(qǐng)請(qǐng)求拒絕IRR是在請(qǐng)求超過(guò)DLE時(shí)發(fā)出的拒絕消息，選擇另一個(gè)最佳轉(zhuǎn)發(fā)器SAOF是發(fā)送到所有節(jié)點(diǎn)的重定向消息；

2)初始信標(biāo)：在初始信標(biāo)期間，水下傳感器節(jié)點(diǎn)在位于傳輸范圍(Ni)之間驗(yàn)證身份，同時(shí)維護(hù)一張[ENS(Ni)]表，[ENS(Ni)]將符合條件的鄰居節(jié)點(diǎn)插入到接收器中，被插入接收器深度小于已發(fā)起請(qǐng)求的節(jié)點(diǎn)的接收器，其中深度測(cè)量為必要條件，深度信息由深度傳感器探測(cè)獲得，當(dāng)傳感器向上轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，就可以在符合條件的鄰居節(jié)點(diǎn)選擇列表[ENS(Ni)]中選擇最佳轉(zhuǎn)發(fā)器進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，防止傳感器節(jié)點(diǎn)向所有鄰居節(jié)點(diǎn)廣播邀請(qǐng)請(qǐng)求，初始信標(biāo)過(guò)程如下：

2-1)較深處傳感器節(jié)點(diǎn)將邀請(qǐng)請(qǐng)求(IR)廣播到[ENS(Ni)]中；

2-2)列出淺深度節(jié)點(diǎn)；

3)動(dòng)態(tài)壽命估計(jì)DLE：假設(shè)同質(zhì)傳感器由S＝{s1，s2，...sn}表示，并且每個(gè)傳感器節(jié)點(diǎn)都能夠基于其本信息即能量、深度，從該組轉(zhuǎn)發(fā)器中選擇最佳轉(zhuǎn)發(fā)器，如公式(1)所示：

只有當(dāng)節(jié)點(diǎn)的剩余能量高于εng(τ)_(k,d)時(shí)，節(jié)點(diǎn)才能將自身聲明為最優(yōu)轉(zhuǎn)發(fā)器，εng(τ)_(k,d)為在距離d上發(fā)送k比特消息所需的最小能量，在通信的初始階段，每個(gè)節(jié)點(diǎn)的剩余能量將近似等于初始能量，節(jié)點(diǎn)的剩余能量表示為公式(2)：

εng_剩余＝εng_初始-εng_消耗 (2)

每個(gè)節(jié)點(diǎn)消耗的能量表示為公式(3)：

εng_消耗＝εng_傳輸+εng_接收 (3)

網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能量估計(jì)DLE表示為公式(4)：

，

則：

3-1)基于動(dòng)態(tài)壽命估計(jì)的接受DLEA(Acceptance based on dynamic life estimate，簡(jiǎn)稱DLEA)：DLEA根據(jù)DLE確定是否可以處理特定請(qǐng)求IR，并根據(jù)單個(gè)節(jié)點(diǎn)的DLE評(píng)估情況發(fā)出IRA或IRR令牌，接收到IR并發(fā)出IRA的淺深度節(jié)點(diǎn)充當(dāng)父節(jié)點(diǎn)，而通過(guò)發(fā)送IRC確認(rèn)IRA的深度節(jié)點(diǎn)充當(dāng)子節(jié)點(diǎn)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都維護(hù)兩個(gè)名為L(zhǎng)OA(List of Acceptances，簡(jiǎn)稱LOA)和LOC(List Of Confirmations，簡(jiǎn)稱LOC)的表，LOA表包含父節(jié)點(diǎn)發(fā)出的IRA，LOC表包含子節(jié)點(diǎn)發(fā)出的IRC，當(dāng)接收到IR時(shí)，父節(jié)點(diǎn)基于DLE來(lái)確定該請(qǐng)求是否在父節(jié)點(diǎn)的容量范圍內(nèi)，如公式(5)所示：

將LOAs、LOCs進(jìn)行計(jì)數(shù)相加，如果當(dāng)前請(qǐng)求的和值小于特定節(jié)點(diǎn)的DLEs，則發(fā)出IRA令牌，并在LOA中添加一個(gè)條目，否則發(fā)出IRR令牌，其中LOA為接受請(qǐng)求條目列表，LOC為確認(rèn)請(qǐng)求條目列表，DLE為特定節(jié)點(diǎn)的動(dòng)態(tài)壽命估計(jì)；

2-3)基于動(dòng)態(tài)壽命估計(jì)的確認(rèn)DLEC(Confirmation based on dynamic lifeestimate,簡(jiǎn)稱DLEC)：DLEC是用來(lái)確定是否可以確認(rèn)收到的IRA，在此階段，子節(jié)點(diǎn)有機(jī)會(huì)根據(jù)能量深度范圍EDR(Energy depth range,簡(jiǎn)稱EDR)信息確認(rèn)最佳父節(jié)點(diǎn)之一，IRA由父節(jié)點(diǎn)在淺層發(fā)布，在接收到IRA令牌之后收到信息的子節(jié)點(diǎn)確認(rèn)淺深度處的最佳轉(zhuǎn)發(fā)器節(jié)點(diǎn)，輪詢基于表中該節(jié)點(diǎn)維護(hù)的EDR信息，如果一個(gè)子節(jié)點(diǎn)收到一個(gè)或一個(gè)以上的IRA令牌，就有機(jī)會(huì)成為上層朝向接收器的最佳節(jié)點(diǎn)，如公式(6)所示：

Max{EDR＝{Em，Dm}；} (6)，

其中Em和Dm是LOA中從接收器到節(jié)點(diǎn)的能量和深度差異，一旦深層節(jié)點(diǎn)通過(guò)基于公式(6)中的條件發(fā)出IRC，則將此條目添加到在LOC中，同時(shí)此節(jié)點(diǎn)向最先發(fā)送IRA請(qǐng)求的淺層節(jié)點(diǎn)發(fā)送通知消息SAOF(Selected Another Optimal Forwarder，簡(jiǎn)稱SAOF)，收到SAOF消息的淺層節(jié)點(diǎn)從LOA中刪除接受條目并更新DLE；

4)初始路徑：連接子節(jié)點(diǎn)和父節(jié)點(diǎn)，從源到目的地建立路徑進(jìn)行數(shù)據(jù)傳輸，在初始階段，較高深度的節(jié)點(diǎn)1發(fā)出IRC到淺層節(jié)點(diǎn)2，將已啟動(dòng)傳輸?shù)墓?jié)點(diǎn)1添加到路徑中，直到節(jié)點(diǎn)2的深度等于sink節(jié)點(diǎn)的深度；

5)群優(yōu)化問(wèn)題求解：采用蝙蝠算法實(shí)現(xiàn)群優(yōu)化問(wèn)題的求解，由Xin-She Yang開(kāi)發(fā)的一種新的元啟發(fā)式搜索算法稱為蝙蝠算法，通過(guò)模擬蝙蝠的回聲定位能力，實(shí)現(xiàn)了群優(yōu)化問(wèn)題的求解，定義w維搜索空間第i個(gè)虛擬蝙蝠位置x_i速度v_i值更新的規(guī)則，其中，i＝1,2,3...n在時(shí)間步長(zhǎng)t新解和速度給出如下公式(7)、(8)和(9)：

f_i＝f_min+(f_max-f_min)β (7)

，

其中β∈[0,1]是服從均勻分布的隨機(jī)向量,x*是當(dāng)前全局最佳位置即解，

比較j個(gè)蝙蝠找到的最優(yōu)解，每個(gè)蝙蝠開(kāi)始時(shí)會(huì)被隨機(jī)分配一個(gè)服從均勻分布[fmin,fmax]的頻率，對(duì)于局部搜索部分，一旦從當(dāng)前最佳解中選擇了一個(gè)解，則使用隨機(jī)游走對(duì)每個(gè)蝙蝠產(chǎn)生一個(gè)新解如公式(10)：

x_new＝x_old+δA^(t) (10)，

其中δ∈[-1,1]是一個(gè)隨機(jī)數(shù)，而是此時(shí)間步長(zhǎng)中所有蝙蝠的平均響度，從實(shí)現(xiàn)的角度來(lái)看，最好能夠提供一個(gè)縮放參數(shù)來(lái)控制步長(zhǎng)，因此，可以將公式(10)改寫(xiě)為公式(11)：

x_new＝x_old+σδ_tA^(t) (11)

其中δ_t服從高斯正態(tài)分布N(0,1)，σ是縮放因子，響度A_i和脈沖發(fā)射率r_i也隨著迭代的進(jìn)行而相應(yīng)地更新，更新公式為公式(12)、公式(13)：

r_i^t+1＝r_i⁰[1-exp(-γt)] (13)

其中α和γ是常數(shù)，對(duì)于任何0＜α＜1和γ＞0，有：

6)改進(jìn)BA的路徑優(yōu)化：

1-6)引入優(yōu)化因子：由于經(jīng)典蝙蝠算法在進(jìn)行迭代優(yōu)化時(shí)會(huì)陷入局部?jī)?yōu)化性，因此引入優(yōu)化因子λ來(lái)對(duì)MOO-BA算法的頻率進(jìn)行優(yōu)化，以此來(lái)達(dá)到全局搜索和局部搜索的平衡，將式公式(7)變更為公式(15)：

f_i＝(f_min+(f_max-f_min)β)λ (15)

公式(16)中ti為當(dāng)前迭代次數(shù)；

2-6)BA優(yōu)化路徑的過(guò)程如下：

步驟1：基于DLE初始化蝙蝠種群X_i和V_i(i＝1,2,...,n)初始化頻率f_i，脈沖發(fā)射率r_i，響度A_i和最大迭代次數(shù)N_max；

步驟2：假設(shè)多目標(biāo)適應(yīng)度函數(shù)為令w_q≥0,則根據(jù)適應(yīng)度函數(shù)計(jì)算適應(yīng)度值，排列蝙蝠，找出當(dāng)前最佳解BB，根據(jù)最佳解BB填充路徑；

步驟3：根據(jù)公式(11)～公式(13)，對(duì)網(wǎng)絡(luò)中的蝙蝠的速度和位置進(jìn)行更新；

步驟4：生成隨機(jī)數(shù)R1,假如R1大于r_i時(shí),從最佳解中選擇一個(gè)BB(解),圍繞BB產(chǎn)生一個(gè)局部解LBB(Local best bat,簡(jiǎn)稱LBB)；

步驟5：生成隨機(jī)數(shù)R2,假如R2小于A_i同時(shí)f(x_i)＜f(x*),將LBB更新為BB，增加r_i減少A_i；

步驟6：經(jīng)過(guò)一段時(shí)間運(yùn)行,對(duì)新的蝙蝠群體進(jìn)行評(píng)估判定,把網(wǎng)絡(luò)中所有的蝙蝠適應(yīng)度值按照從大到小順序排列，找到最小值以及對(duì)應(yīng)的位置，就是當(dāng)前最優(yōu)解和最優(yōu)值；

步驟7：重復(fù)執(zhí)行步驟2)～步驟5)，直到滿足設(shè)定的最優(yōu)解條件或達(dá)到最大迭代次數(shù)；

步驟8：輸出全局最優(yōu)值和最優(yōu)解：上述蝙蝠算法過(guò)程將蝙蝠行為捕獲到適應(yīng)度函數(shù)中，目標(biāo)是建立具有最小延遲和最大輸送比的優(yōu)化路徑，通過(guò)DLE改變X_i和V_i，在從源到目的地的初始填充期間填充機(jī)會(huì)路徑，適應(yīng)度函數(shù)具有歸一化的多目標(biāo)權(quán)重，傳遞比mo1和延遲mo2由公式(17)獲得：

其中W^mo1＝1-mo1，W^mo2＝mo2.

針對(duì)最初填充的路徑計(jì)算并且排名基于權(quán)重的適應(yīng)度函數(shù)，具有最小適應(yīng)度的路徑被命名為最佳蝙蝠B(yǎng)B，如式(18)所示：

其中pi是最初填充的路徑，P是最初填充的路徑中的BA路徑。