[發(fā)明專利]最短信息收集路徑的搜索方法、系統(tǒng)、存儲(chǔ)介質(zhì)及應(yīng)用

有效

• 申請?zhí)枺?/td>: 202010197684.4
• 申請日: 2020-03-19
• 公開（公告）號(hào): CN111556546B
• 公開（公告）日: 2022-08-23
• 發(fā)明（設(shè)計(jì)）人: 黃鵬宇;王薇;武福平;劉勤
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號(hào): H04W40/10
• 分類號(hào): H04W40/10;H04W40/12;G06N3/00;H04W4/70;H04W40/22;H04W84/18
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 黃偉洪

1.一種最短信息收集路徑的搜索方法，其特征在于將路徑表示為一個(gè)粒子，粒子由若干有序節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)表示一個(gè)信息收集點(diǎn)RP的位置坐標(biāo)；使用單個(gè)粒子，將移動(dòng)sink最佳信息收集路徑的全局搜索問題，轉(zhuǎn)化為單個(gè)粒子上各節(jié)點(diǎn)在空間中的隨機(jī)搜索問題；搜索過程中，每次隨機(jī)挑選一個(gè)節(jié)點(diǎn)；使用預(yù)先構(gòu)建的非均勻搜索柵格進(jìn)行搜索，將節(jié)點(diǎn)在覆蓋范圍內(nèi)的連續(xù)搜索轉(zhuǎn)化為搜索柵格上的離散搜索；

所述最短信息收集路徑的搜索方法包括：

第一步，初始化一條有效的信息收集路徑；

第二步，將信息收集路徑轉(zhuǎn)換為一個(gè)有序的信息收集點(diǎn)RP位置鏈表；依照初始路徑中各個(gè)RP的先后次序，將每個(gè)RP的位置坐標(biāo)作為一個(gè)維度，構(gòu)建一個(gè)有序的多維度鏈表，并將該結(jié)構(gòu)稱為一個(gè)粒子；

第三步，隨機(jī)選取粒子中的一個(gè)RP位置，根據(jù)預(yù)先設(shè)置的搜索柵格進(jìn)行隨機(jī)搜索，以獲取更好的信息收集點(diǎn)位置；

第四步，遍歷粒子各個(gè)維度，合并過于接近的相鄰維度；

第五步，計(jì)算粒子對應(yīng)的信息收集路徑長度，即適應(yīng)值；

第六步，迭代執(zhí)行第三步-第五步，直至粒子的適應(yīng)值不再降低為止；

第七步，輸出粒子所表示的信息收集路徑及其適應(yīng)值；

第三步在粒子中隨機(jī)選擇信息收集點(diǎn)位置進(jìn)行柵格搜索包括：

(1)在粒子中隨機(jī)選擇一個(gè)維度，稱為原維度，原維度對應(yīng)的位置坐標(biāo)稱為原維度位置坐標(biāo)；

(2)構(gòu)建一個(gè)搜索柵格，將搜索柵格疊加到選出的原維度位置坐標(biāo)上，根據(jù)柵格獲取備選位置坐標(biāo)集合；

(3)設(shè)sensor節(jié)點(diǎn)與移動(dòng)sink節(jié)點(diǎn)的通信半徑都為R，設(shè)移動(dòng)sink節(jié)點(diǎn)位于原維度位置坐標(biāo)上時(shí)所能覆蓋的sensor節(jié)點(diǎn)集合為原覆蓋sensor節(jié)點(diǎn)集合，在備選位置集合中逐一判定、選出移動(dòng)sink節(jié)點(diǎn)位于備選位置上時(shí)所能覆蓋的sensor節(jié)點(diǎn)集合能夠完全包含原覆蓋sensor節(jié)點(diǎn)集合的備選位置坐標(biāo)，構(gòu)成終選位置坐標(biāo)集合；

(4)從終選位置坐標(biāo)集合中選取使移動(dòng)sink的信息收集路徑長度縮短最多的位置坐標(biāo)作為原維度位置坐標(biāo)的替換位置坐標(biāo)，更新粒子；

所述第四步遍歷粒子各維度進(jìn)行相鄰維度合并包括：從前向后遍歷粒子的各個(gè)維度，判斷當(dāng)前維度位置坐標(biāo)與路徑上前后2個(gè)相鄰維度位置坐標(biāo)之間的間距，如果間距小于0.1R，則分別統(tǒng)計(jì)前后兩個(gè)相鄰維度位置坐標(biāo)上移動(dòng)sink節(jié)點(diǎn)所能覆蓋的sensor節(jié)點(diǎn)集合；如果前后2個(gè)相鄰維度位置坐標(biāo)上能夠覆蓋的sensor節(jié)點(diǎn)集合存在包含關(guān)系，則保留能夠覆蓋更多sensor節(jié)點(diǎn)的維度坐標(biāo)，刪除覆蓋較少sensor節(jié)點(diǎn)的維度坐標(biāo)，若覆蓋的sensor節(jié)點(diǎn)集合相同時(shí)，則隨機(jī)刪除一個(gè)維度坐標(biāo)。

2.如權(quán)利要求1所述的最短信息收集路徑的搜索方法，其特征在于，所述最短信息收集路徑的搜索方法構(gòu)建了一個(gè)4層32個(gè)柵格點(diǎn)的多層圓形柵格結(jié)構(gòu)，根據(jù)新舊信息收集點(diǎn)通信范圍的重疊面積與舊信息收集點(diǎn)通信范圍面積的百分比設(shè)置4層圓形柵格，由內(nèi)至外分別表示重疊率為95％、90％、80％、70％時(shí)的搜索柵格，每層圓環(huán)結(jié)構(gòu)的半徑由重疊百分比和節(jié)點(diǎn)的通信半徑計(jì)算得出，每層圓環(huán)結(jié)構(gòu)上設(shè)置相同數(shù)量的柵格點(diǎn)；將柵格中的柵格位置標(biāo)記為其中下標(biāo)i表示是由內(nèi)至外的第幾層?xùn)鸥瘢瑪?shù)值表示對應(yīng)的重疊率，上標(biāo)k表示從90°開始的柵格位置標(biāo)識(shí)，從1到8分別表示{90°，45°，0°，-45°，-90°，-135°，-180°，-225°}方向上的柵格點(diǎn)。

3.如權(quán)利要求1所述的最短信息收集路徑的搜索方法，其特征在于，所述第六步包括計(jì)算粒子的適應(yīng)值，適應(yīng)值是判定信息收集路徑是否有效的依據(jù)，選擇粒子對應(yīng)的路徑長度作為粒子的適應(yīng)值，適應(yīng)值越小代表路徑效果越好；

迭代的退出條件設(shè)置為：搜索獲得的適應(yīng)值如果在100次迭代中適應(yīng)值的減少率沒有達(dá)到1/100，則退出，并輸出最佳路徑及最佳路徑對應(yīng)的適應(yīng)值，若算法沒有退出則返回第二步繼續(xù)進(jìn)行迭代。