[發(fā)明專利]基于鄰接矩陣的水下傳感器網(wǎng)絡(luò)的柵欄覆蓋方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710997617.9
• 申請(qǐng)日: 2017-10-24
• 公開(kāi)（公告）號(hào): CN107770784B
• 公開(kāi)（公告）日: 2021-03-23
• 發(fā)明（設(shè)計(jì)）人: 申曉紅;常娟;姚海洋;賈天一;柳溪;劉鐳;李芾龍
• 申請(qǐng)（專利權(quán)）人: 西北工業(yè)大學(xué)
• 主分類號(hào): H04W16/18
• 分類號(hào): H04W16/18;H04W40/02;H04W40/24;H04W84/18
• 代理公司: 西北工業(yè)大學(xué)專利中心 61204
• 代理人: 顧潮琪

1.一種基于鄰接矩陣的水下傳感器網(wǎng)絡(luò)的柵欄覆蓋方法，其特征在于包括下述步驟：

第一步，對(duì)傳感器網(wǎng)絡(luò)中隨機(jī)部署的所有傳感器按照位置橫坐標(biāo)由左向右升序排列，橫坐標(biāo)相同的傳感器按照位置縱坐標(biāo)升序排列，并對(duì)每個(gè)傳感器采用s₁～s_N進(jìn)行標(biāo)識(shí)，形成傳感器網(wǎng)絡(luò)圖；

第二步，構(gòu)建傳感器網(wǎng)絡(luò)的覆蓋圖，具體步驟如下：

(1)如果目標(biāo)以垂直路徑自上而下穿越監(jiān)測(cè)區(qū)域，則構(gòu)建弱柵欄覆蓋，將每個(gè)傳感器作為覆蓋圖的頂點(diǎn)；若其中兩頂點(diǎn)s_i和s_j的橫坐標(biāo)距離|x_j-x_i|≤2R_s，j＞i，R_s表示傳感器的感知半徑，則將這兩頂點(diǎn)之間用直線連接作為覆蓋圖的邊，否則頂點(diǎn)s_i與s_j及其右邊的所有頂點(diǎn)之間不存在邊；

(2)如果目標(biāo)以任意路徑自上而下穿越監(jiān)測(cè)區(qū)域，則構(gòu)建強(qiáng)柵欄覆蓋，將每個(gè)傳感器作為覆蓋圖的頂點(diǎn)；若其中兩頂點(diǎn)s_i和s_j的歐氏距離d(s_i,s_j)≤2R_s，則將這兩頂點(diǎn)之間用直線連接作為覆蓋圖的邊，否則頂點(diǎn)s_i與s_j及其右邊的所有頂點(diǎn)之間不存在邊；

第三步，根據(jù)覆蓋圖建立UT-鄰接矩陣，具體步驟如下：

(1)弱柵欄對(duì)應(yīng)的鄰接矩陣A_w＝(a_ij)_N×N，其中元素a_ij表示覆蓋圖中頂點(diǎn)s_i和s_j之間的位置關(guān)系，若s_i和s_j之間存在邊則a_ij＝1，否則a_ij＝0；

(2)強(qiáng)柵欄對(duì)應(yīng)的鄰接矩陣為A_s＝(a_ij)_N×N，其中元素a_ij表示覆蓋圖中頂點(diǎn)s_i和s_j之間的位置關(guān)系，若s_i和s_j之間存在邊則a_ij＝1，否則a_ij＝0；

第四步，搜索與區(qū)域左邊界距離小于R_s的傳感器s_i作為所構(gòu)建柵欄的第一個(gè)節(jié)點(diǎn)；若存在多個(gè)與左邊界距離小于R_s的傳感器，取其中橫坐標(biāo)最大的傳感器作為第一個(gè)節(jié)點(diǎn)；若不存在與左邊界距離小于R_s的傳感器，則該傳感器網(wǎng)絡(luò)無(wú)法構(gòu)建柵欄；

第五步，轉(zhuǎn)至鄰接矩陣的第i行，選取該行最右邊為1的元素a_i,j，節(jié)點(diǎn)s_j為構(gòu)建柵欄所需的下一個(gè)節(jié)點(diǎn)；

重復(fù)第五步操作，直到搜索的節(jié)點(diǎn)與區(qū)域右邊界距離小于R_s，該節(jié)點(diǎn)為所構(gòu)建柵欄的最后一個(gè)節(jié)點(diǎn)。

2.根據(jù)權(quán)利要求1所述的基于鄰接矩陣的水下傳感器網(wǎng)絡(luò)的柵欄覆蓋方法，其特征在于：當(dāng)且僅當(dāng)移動(dòng)目標(biāo)所有垂直穿越監(jiān)測(cè)區(qū)域的路徑與k個(gè)不同傳感器的感知區(qū)域相交時(shí)，此傳感器網(wǎng)絡(luò)就為k-弱柵欄覆蓋，在第一步之后首先搜索確定與區(qū)域左邊界距離小于R_s的所有p個(gè)傳感器和與區(qū)域右邊界距離小于R_s的所有q個(gè)傳感器，確定該傳感器網(wǎng)絡(luò)能夠構(gòu)建的最大柵欄數(shù)k≤min{p,q}，若不存在與左邊界或右邊界距離小于R_s的傳感器，則該傳感器網(wǎng)絡(luò)無(wú)法構(gòu)建柵欄；然后按照弱柵欄覆蓋構(gòu)建傳感器網(wǎng)絡(luò)的覆蓋圖并根據(jù)覆蓋圖建立UT-鄰接矩陣；最終，分別以與區(qū)域左邊界距離小于R_s的各個(gè)傳感器為柵欄的第一個(gè)節(jié)點(diǎn)，轉(zhuǎn)至鄰接矩陣的第i行，選取該行最右邊為1的元素a_i,j，節(jié)點(diǎn)s_j為構(gòu)建柵欄所需的下一個(gè)節(jié)點(diǎn)來(lái)構(gòu)建柵欄；每構(gòu)建完成一個(gè)柵欄覆蓋，就將該柵欄中的所有傳感器對(duì)應(yīng)的原UT-鄰接矩陣中的行和列中全部元素置為0；重復(fù)構(gòu)建柵欄，直到構(gòu)建的柵欄數(shù)等于確定的最大柵欄數(shù)或無(wú)法構(gòu)建完整柵欄為止。

3.根據(jù)權(quán)利要求1所述的基于鄰接矩陣的水下傳感器網(wǎng)絡(luò)的柵欄覆蓋方法，其特征在于：當(dāng)且僅當(dāng)移動(dòng)所有穿越帶狀區(qū)域的路徑與k個(gè)不同傳感器的感知區(qū)域相交時(shí)，此傳感器網(wǎng)絡(luò)稱為k-強(qiáng)柵欄覆蓋，在第一步之后首先搜索確定與區(qū)域左邊界距離小于R_s的所有p個(gè)傳感器和與區(qū)域右邊界距離小于R_s的所有q個(gè)傳感器，確定該傳感器網(wǎng)絡(luò)能夠構(gòu)建的最大柵欄數(shù)k≤min{p,q}，若不存在與左邊界或右邊界距離小于R_s的傳感器，則該傳感器網(wǎng)絡(luò)無(wú)法構(gòu)建柵欄；然后按照強(qiáng)柵欄覆蓋構(gòu)建傳感器網(wǎng)絡(luò)的覆蓋圖并根據(jù)覆蓋圖建立UT-鄰接矩陣；最終，分別以與區(qū)域左邊界距離小于R_s的各個(gè)傳感器為柵欄的第一個(gè)節(jié)點(diǎn)，轉(zhuǎn)至鄰接矩陣的第i行，選取該行最右邊為1的元素a_i,j，節(jié)點(diǎn)s_j為構(gòu)建柵欄所需的下一個(gè)節(jié)點(diǎn)來(lái)構(gòu)建柵欄；每構(gòu)建完成一個(gè)柵欄覆蓋，就將該柵欄中的所有傳感器對(duì)應(yīng)的原UT-鄰接矩陣中的行和列中全部元素置為0；重復(fù)構(gòu)建柵欄，直到構(gòu)建的柵欄數(shù)等于確定的最大柵欄數(shù)或無(wú)法構(gòu)建完整柵欄為止。