[發(fā)明專利]基于貪婪子模的無線可充電傳感器網絡充電器部署方法

有效

• 申請?zhí)枺?/td>: 202010090862.3
• 申請日: 2020-02-13
• 公開（公告）號: CN111277951B
• 公開（公告）日: 2021-04-06
• 發(fā)明（設計）人: 徐佳;蔡威;徐力杰
• 申請（專利權）人: 南京郵電大學
• 主分類號: H04W4/02
• 分類號: H04W4/02;H04W16/18;H04W84/18;H02J50/20;H02J7/02;B60L53/12;B60L53/00
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

1.一種基于貪婪子模的無線可充電傳感器網絡充電器部署方法，其特征在于，包括以下步驟：

(1)根據(jù)各個移動小車周期性的移動路線、移動過程中的電量消耗率、在路線上各個監(jiān)測點的停留時間，以及各個監(jiān)測點之間的距離等信息，通過以最小化充電功率為目標構建求解無線充電器最優(yōu)部署方案的0-1整數(shù)規(guī)劃模型；

(2)根據(jù)步驟(1)建立的0-1整數(shù)規(guī)劃模型，構造單調增的子模函數(shù)；

(3)采用貪婪算法選出部署無線充電器的監(jiān)測點位置，從而最終得到部署方案；

所述步驟(1)具體包括以下步驟：

(11)網絡中移動小車的集合V＝{v₁，v₂，...v_m}，監(jiān)測點的集合S＝{s₁，s₂，..s_n}，設任意小車v_i∈V移動路線所經過的監(jiān)測點順序集合其中且n_i表示小車v_i的移動路線經過的監(jiān)測點數(shù)量，對于任意監(jiān)測點令和分別表示小車v_i在的停留充電時間和充電效率，因此，可以建模得到小車v_i在監(jiān)測點的停留時間內能夠獲得的充電電量其中是監(jiān)測點允許部署的充電器充電功率，是一個二元變量，當且僅當在監(jiān)測點部署充電器；

(12)通過計算出任意小車v_i從監(jiān)測點移動到其路線的下一個監(jiān)測點所消耗的能量，其中表示小車v_i移動路線上的監(jiān)測點到其下一個監(jiān)測點之間的距離，ρ_i表示小車v_i移動過程中的電量消耗率；這里，若j∈[1，n_i-1]，監(jiān)測點在小車v_i的移動路線上的下一個監(jiān)測點是若j＝n_i，監(jiān)測點在小車v_i的移動路線上的下一個監(jiān)測點是

(13)令表示小車v_i在監(jiān)測點執(zhí)行監(jiān)測任務消耗的能量，依次建模出任意小車v_i在每個監(jiān)測點停留時間結束后的剩余能量初始地，其中I表示小車v_i在起始監(jiān)測點的初始能量，設置初始能量以保證v_i在監(jiān)測點能夠初始地完成首次監(jiān)測任務，得到初始位置的剩余能量當j∈[2，n_i]時，當小車v_i一個移動周期結束回到監(jiān)測點準備進入下一個移動周期時，

(14)對于任意小車v_i和其路線上的任意監(jiān)測點須滿足其中，當j∈[1，n_i-1]時，當j＝n_i時，為了保證上述約束的前提下實現(xiàn)充電功率最小化，構造得到0-1整數(shù)規(guī)劃模型如下：

所述步驟(2)包括以下步驟：

(21)通過分析，0-1整數(shù)規(guī)劃模型(1)中實際有個包含了x(s₁)，x(s₂)，...，x(s_n)這n個變量的不等式約束條件，因此，模型(1)可以等價地變換為如下的形式：

其中，且a_ij和b_i是可通過模型(1)計算得到的非負參數(shù)，即

(22)根據(jù)模型(2)構造函數(shù)f如下：對于任意一個集合定義f(X)是一個單調增的子模函數(shù)；模型(2)的優(yōu)化問題轉換為一個最小權子模覆蓋問題，即如何找到一個集合以使得∑_j∈Xp(s_j)最小化，其中集合X必須滿足以下約束條件：對所有x∈X，都有f(X∪{x})＝f(X)；

所述步驟(3)包括如下步驟：

(31)初始化設置集合

(32)令I(X)＝{i|∑_l∈Xa_il＜b_i}，通過貪心策略在每一次迭代過程中將指標j，j∈{1，...，n}，添加進集合X中，使得達到最大值，直至對所有j∈{1，...，n}都不存在∑_i∈I(X)min{a_ij，b_i-∑_l∈Xa_il}＞0為止；

(33)在經過步驟(32)的迭代后得到最終的集合X，得最優(yōu)部署充電器的監(jiān)測點集合S^*＝{s_j|j∈X}，該部署方法的近似比為1+lnγ，這里的