[發(fā)明專利]一種動(dòng)態(tài)k值分簇路由方法

有效

• 申請?zhí)枺?/td>: 201410794524.2
• 申請日: 2014-12-18
• 公開（公告）號(hào): CN104469879B
• 公開（公告）日: 2018-10-09
• 發(fā)明（設(shè)計(jì)）人: 吳黎兵;聶雷;杜錦;彭紅梅;鄒逸飛
• 申請（專利權(quán)）人: 武漢大學(xué)
• 主分類號(hào): H04W40/10
• 分類號(hào): H04W40/10;H04W84/18
• 代理公司: 武漢科皓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 張火春

1.一種動(dòng)態(tài)k值分簇路由方法，其特征在于，包括如下步驟：

步驟1，在監(jiān)測區(qū)域部署基站和傳感器節(jié)點(diǎn)，傳感器節(jié)點(diǎn)開始工作并自組織形成無線傳感器網(wǎng)絡(luò)；

步驟2，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)向基站發(fā)送包括自身位置和剩余能量信息的數(shù)據(jù)包；基站收集到所有節(jié)點(diǎn)的數(shù)據(jù)包后，計(jì)算當(dāng)前網(wǎng)絡(luò)中存活節(jié)點(diǎn)的剩余能量平均值E_average，并選擇節(jié)點(diǎn)剩余能量高于E_average的節(jié)點(diǎn)作為候選簇頭，生成候選簇頭集合；

步驟3，基站求解最佳分簇方式，同時(shí)計(jì)算網(wǎng)絡(luò)有效k值NK，并將這些分簇信息廣播；

步驟4，網(wǎng)絡(luò)中的節(jié)點(diǎn)接收到基站廣播的分簇信息包后，查找自身所在簇的簇頭ID；如果自身ID與所在簇的簇頭ID相同，則節(jié)點(diǎn)自身當(dāng)選為簇頭，同時(shí)節(jié)點(diǎn)根據(jù)簇頭ID遍歷分簇信息包，收集簇內(nèi)所有成員節(jié)點(diǎn)的ID信息；如果節(jié)點(diǎn)收到分簇信息包后發(fā)現(xiàn)自身為普通節(jié)點(diǎn)，那么節(jié)點(diǎn)進(jìn)入等待狀態(tài)，直到收到所在簇的簇頭廣播消息報(bào)文，其中包含簇內(nèi)各節(jié)點(diǎn)的分配時(shí)隙，簇內(nèi)節(jié)點(diǎn)從消息報(bào)文中獲取自身發(fā)送數(shù)據(jù)的時(shí)隙；

步驟5，進(jìn)入數(shù)據(jù)傳輸?shù)姆€(wěn)定階段，簇內(nèi)節(jié)點(diǎn)在指定時(shí)隙發(fā)送自身收集的數(shù)據(jù)信息給所在簇的簇頭，簇頭收到所有成員節(jié)點(diǎn)發(fā)來的數(shù)據(jù)信息后，將數(shù)據(jù)進(jìn)行融合并轉(zhuǎn)發(fā)給基站，穩(wěn)定階段結(jié)束后轉(zhuǎn)步驟6；

步驟6，網(wǎng)絡(luò)已完成一個(gè)周期的第1輪，隨后進(jìn)入局部選簇流程，即在接下來的NK輪將保持分簇結(jié)構(gòu)不變，只在每個(gè)簇內(nèi)進(jìn)行簇頭更新；局部選簇結(jié)束后轉(zhuǎn)步驟7；

步驟7，判斷網(wǎng)絡(luò)中節(jié)點(diǎn)是否全部死亡，是則結(jié)束當(dāng)前流程，否則轉(zhuǎn)步驟2；

所述的網(wǎng)絡(luò)有效k值的計(jì)算方法如下：

假設(shè)第1輪選簇完成后網(wǎng)絡(luò)中有m個(gè)簇，簇的編號(hào)分別為C₁、C₂、…、C_m，每個(gè)簇中的節(jié)點(diǎn)個(gè)數(shù)分別為N₁、N₂、...、N_m，簇頭節(jié)點(diǎn)編號(hào)分別為CH₁、CH₂、...、CH_m，對于第i個(gè)簇，簇中N_i個(gè)節(jié)點(diǎn)的編號(hào)分別為C_i1、C_i2、…、_{，為了計(jì)算網(wǎng)絡(luò)有效k值，引入“平行簇頭”、“簇內(nèi)有效k值”和“網(wǎng)絡(luò)有效k值”的概念；}

依據(jù)公式(1)計(jì)算節(jié)點(diǎn)擔(dān)任簇頭的能力；

其中C_ij表示第i個(gè)簇中編號(hào)為j的節(jié)點(diǎn)，T(C_ij)表示節(jié)點(diǎn)C_ij的能力權(quán)值，E(C_ij)表示節(jié)點(diǎn)的剩余能量，表示節(jié)點(diǎn)到基站的距離，表示節(jié)點(diǎn)到簇內(nèi)其他節(jié)點(diǎn)距離的平方和，p為平衡因子，同時(shí)有：

其中表示第i個(gè)簇中編號(hào)為j的節(jié)點(diǎn)到編號(hào)為h的節(jié)點(diǎn)的距離；平衡因子p用來調(diào)節(jié)節(jié)點(diǎn)到基站距離與節(jié)點(diǎn)在簇中位置對節(jié)點(diǎn)擔(dān)任簇頭的影響，p的值介于0到1之間；

定義1.平行簇頭：如果節(jié)點(diǎn)C_ij的能力權(quán)值大于或等于所在簇的簇頭CH_i的能力權(quán)值T(CH_i)，則該節(jié)點(diǎn)為簇的平行簇頭，即有T(C_ij)≥T(CH_i)；

定義2.簇內(nèi)有效k值：網(wǎng)絡(luò)中單個(gè)簇可以進(jìn)行局部簇頭更新的次數(shù)稱為該簇的簇內(nèi)有效k值k(C_i)，如果簇C_i的平行簇頭個(gè)數(shù)為z，那么有k(C_i)＝z；

依據(jù)定義1找出網(wǎng)絡(luò)中每個(gè)簇的平行簇頭，現(xiàn)假設(shè)簇C_i的平行簇頭個(gè)數(shù)為z，那么簇C_i可以進(jìn)行局部簇頭更新的次數(shù)為z，將一個(gè)簇可以進(jìn)行局部簇頭更新的次數(shù)作為該簇的簇內(nèi)有效k值；

當(dāng)簇頭是簇中能力權(quán)值最大的節(jié)點(diǎn)時(shí)，z的值為0；在計(jì)算簇內(nèi)有效k值時(shí)設(shè)置了一個(gè)下限值x，改進(jìn)的簇內(nèi)有效k值計(jì)算方法如下：

k(C_i)＝max{x,z}(2≤x≤5) (3)

其中下限值x取2到5之間的隨機(jī)整數(shù)；

定義3.網(wǎng)絡(luò)有效k值：網(wǎng)絡(luò)中一個(gè)周期內(nèi)所有簇進(jìn)行簇頭更新的次數(shù)，記為NK；

通過公式(3)求出網(wǎng)絡(luò)中每個(gè)簇的簇內(nèi)有效k值，將簇內(nèi)所有節(jié)點(diǎn)到基站距離的平均值作為簇到基站的距離，將簇到基站的距離與網(wǎng)絡(luò)中簇到基站距離最大值的比值平方，作為簇內(nèi)有效k值相對于網(wǎng)絡(luò)有效k值的權(quán)重因子；簇到基站距離的計(jì)算方法如公式(4)所示；

其中表示節(jié)點(diǎn)C_ij到基站的距離；

簇C_i權(quán)重因子的計(jì)算方法如公式(5)所示；

其中D(C_i)表示簇C_i到基站的距離，D_max表示網(wǎng)絡(luò)中簇到基站距離的最大值；

結(jié)合公式(3)、(4)和(5)，推導(dǎo)出網(wǎng)絡(luò)有效k值的計(jì)算公式如下：

其中WF(C_i)表示簇C_i的權(quán)重因子，k(C_i)表示簇C_i的簇內(nèi)有效k值。