[發明專利]一種面向多跳無線充電的綜合成本優化及成本分攤方法

有效

• 申請號: 202110229088.4
• 申請日: 2021-03-02
• 公開（公告）號: CN113034172B
• 公開（公告）日: 2022-08-26
• 發明（設計）人: 徐佳;吳思徐;周凱軍;薛剛;駱健;徐力杰;魯蔚鋒;蔣凌云
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06Q30/02
• 分類號: G06Q30/02;G06Q50/06;G06F16/901;G06F30/20;G06F111/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

1.一種面向多跳無線充電的綜合成本優化及成本分攤方法，其特征在于，包括以下步驟：

(1)建立多跳無線充電傳感網絡，形式化充電器部署的綜合成本最小化問題；

(2)采用面向多跳無線充電的綜合成本優化算法，得到充電器部署方案，并計算綜合成本；

(3)采用面向多跳無線充電的成本分攤方案，將綜合成本分配到每一個傳感器節點上；

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

(21)形式化出與多跳充電器節點部署的綜合成本最小化問題等價的覆蓋問題，其中覆蓋一個傳感器節點是指該傳感器節點的能量需求被滿足：

約束：

其中，T_i表示令以i為根的充電樹，且T_i＝(V_i,E_i)，其中V_i為充電樹T_i中傳感器節點位置的集合，E_i為充電樹T_i中的邊集合，為充電森林，是所有充電樹的集合，即F(T_i)是充電樹T_i的綜合成本，若值為否則值為0；所有充電樹的綜合成本之和就是總的綜合成本，約束(8)、(9)確保所有傳感器節點的充電需求都能被滿足，且一個傳感器節點只由一個充電器提供能量，約束(10)確保充電樹上的總能量消耗不超過電池容量上限；

(22)對于每一個可部署充電器位置i∈V，在位置i部署充電器，令以i為根的充電樹為T_i＝(V_i,E_i)，其中V_i為充電樹T_i的節點集，E_i為充電樹T_i的邊集，V_i,E_i最初都是空集；

(23)初始化未覆蓋傳感器節點集V_u＝V，當前充電器可部署位置集V_c＝V，充電森林

(24)若執行步驟(25)到步驟(27)，否則執行步驟(28)；

(25)對于每一個i∈V_c，找到以該位置為根的，總能耗不超過D_MAX的最佳擴展樹T*_i,其中最佳擴展樹滿足其中，稱為平均邊際綜合成本；T'_i是擴展樹，V'_i是擴展樹中的節點集；

(26)對于每一個i∈V_c，找出平均邊際綜合成本最小的那棵充電樹，設該充電樹為T_i；

(27)將T_i中的傳感器節點從未覆蓋傳感器節點集中刪去，即V_u＝V_u\V_i，將充電樹T_i更新為對應的最佳擴展樹，即T_i＝T*_i，將除根節點之外新加入的傳感器節點從當前充電器可部署位置集中刪去，即V_c＝V_c\{V_i\{i}}，返回步驟(24)；

(28)返回充電森林充電森林中所有充電樹的樹根位置構成充電器集合C，表示充電器被設置在這些位置上，按照充電樹的形狀，從根節點傳輸能量；

所述步驟(3)實現過程如下：

對于任何一個位于位置j的傳感器節點，找到覆蓋這個傳感器節點的充電樹，該充電樹的根在i位置，則充電樹表示為T_i，且有j∈V_i，則該傳感器節點需要分攤的成本由以下公式得出：

其中，表示為了滿足充電需求，充電器實際需要能量成本，表示和充電樹中所有傳感器節點一起均分充電器部署成本，傳感器節點所需要分攤的綜合成本為能量成本和部署成本之和；

步驟(25)所述的總能耗不超過D_MAX的最佳擴展樹計算過程如下：

(251)初始化充電器的剩余能量初始化增加傳感器節點數m＝0，初始化V_i(m)＝V_i，E_i(m)＝E_i，令T_i(m)表示在T_i的基礎上增加了m個傳感器節點之后得到的充電樹，初始化當前未覆蓋位置集V'_u＝V_u，初始化最終增加的傳感器節點數m_MIN＝0；

(252)若以i為根節點的充電樹為空，即將根節點加入充電樹，令m＝m+1，V_i(m)＝V_i(m-1)∪{i}，更新剩余能量D_r＝D_r-D_i，更新當前未覆蓋位置集V'_u＝V'_u\{i}；

(253)如果D_r＞0，則重復執行步驟(254)到步驟(255)；否則進入步驟(256)；

(254)找到能耗最小的傳感器節點，不妨設該節點位于j_o，使得所耗費的能量最小，即的值最小，其中j_i為當前充電樹T_i(m)中的傳感器節點所在位置，j_o是當前充電樹T_i(m)外的傳感器節點所在位置；

(255)如果充電器的剩余能量足夠給位于j_o的傳感器節點充電，即則令m＝m+1，V_i(m)＝V_i(m-1)∪{j_o}，V'_u＝V'_u\{j_o}，E_i(m)＝E_i(m-1)∪(j_i,j_o)；否則進入步驟(256)；

(256)找出平均邊際綜合成本最小的情況，將該情況作為最佳擴展樹輸出，即令返回T_i(m_MIN)。