[發明專利]一種基于逆向拍賣策略的無線傳感器網絡中復雜任務協作求解方法

有效

• 申請號: 201310731927.8
• 申請日: 2013-12-26
• 公開（公告）號: CN103686777B
• 公開（公告）日: 2016-10-19
• 發明（設計）人: 王峰;韓光潔;仇浩;張晨語;江旭;錢愛華;鮑娜
• 申請（專利權）人: 河海大學常州校區
• 主分類號: H04W40/32
• 分類號: H04W40/32;H04W84/18;G06F19/00
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

[0001]?技術領域

本發明屬于無線多媒體傳感器網絡領域，具體地本發明涉及一種基于逆向拍賣策略的無線傳感器網絡中復雜任務協作求解方法，將網絡中的復雜任務分簇處理，可提高任務處理效率，平衡網絡負載，延長網絡壽命。?

背景技術

相關文獻如下：?

1、2007年，朱敬華等人在《無線傳感器網絡中能源高效的任務分配算法》中提出多跳傳感器網絡中的一種基于遺傳算法的嵌套優化技術的任務分配算法，通過結合基于遺傳算法的任務映射、路由路徑分配、任務調度以及動態電壓調制來獲得最優分配方案，同時實現應用的實時性和能源利用的高效性。?

2、2010年，Sherine?Abdelhak等在《Energy-balancing?Task?Allocation?on?Wireless?Sensor?Networks?for?Extending?the?Lifetime》中提出了一種任務分組方法，該方法可以保證任務的并行處理，但是當同一個孩子任務有若干個父任務，并且該子任務被同時要求加入不同父任務的任務小組的情況沒有提供相應解決方案。同時，該任務分配方案中也缺少相應的節能措施，僅僅是根據節點的剩余能量來選擇工作節點，不能達到系統性能的最優化。?

3、2011年，Morteza?Okhovvat等人《Task?Allocation?to?Actors?in?Wireless?Sensor?Actor?Networks:An?Energy?And?Time?Aware?Technique》提出了一種基于排隊論優化的任務分配機制，該機制既考慮了系統能量優化又考慮了任務的完成時間。算法的第一階段，任務被平均的分配給每一個代理服務器，并根據這些代理服務器的處理效果來判斷服務器的處理性能；第二階段是根據服務器的處理性能來分配任務。以此方法來達到縮短任務處理時間的目的，但是在無線傳感器網絡中，節點能量受限且難以補充，節點的剩余能量也會隨著處理任務個數的增多而減少，其任務處理性能直接受到影響，不可能一直保持不變。?

發明內容

為了克服現有技術中存在的不足，本發明提供了一種基于逆向拍賣策略的無線傳感器網絡中復雜任務協作求解方法。?

一種基于逆向拍賣策略的無線傳感器網絡中復雜任務協作求解方法，包括如下步驟：?

（1）任務分層，根據任務DAG圖對其進行分層劃分，任務分配時從上至?下逐層分配，每層分布有若干簇；?

（2）當任務事件發生后，事發點所在的簇作為中心簇，中心簇的簇頭負責將層中任務進行分配，當中心簇的簇能量消耗度超過閾值時，則向周邊一跳簇發送請求信息，如果周邊一跳簇能量消耗度未超過閾值，則接受請求，作為中心簇的協作簇；中心簇與周邊一跳簇形成協作簇群，周邊一跳簇簇頭接受中心簇頭的安排；?

（3）中心簇將未分配任務分配到協作簇，分配時保證各個簇的能量均衡，能量消耗度相差最小；任務分配時從上至下逐層分配，第一層的任務需分配到中心簇；在第一層任務處理的同時，進行第二層任務分配，從而縮短任務的完成時間；?

（4）任務分配到中心簇或協作簇的簇頭后，簇頭再將任務分配到簇內成員節點上進行處理，將博弈論引入任務分配中，采用拍賣形式，拍賣策略為第二低價密封拍賣；出價最低的節點中標，并以第二低的價格完成交易，進行處理任務。?

上述步驟（1）中的根據任務的DAG圖對任務進行分層劃分的步驟如下：?

（2a）入口任務劃分為第一層;?

（2b）如果某一子任務前驅最大層為k，則該子任務劃分到k+1層。?

上述步驟（2）中判斷中心簇接受新任務后是否超過自身的簇能量消耗度的計算過程如下：?

（1）計算簇當前能量消耗C(Cluster_i)：簇當前能量消耗是指某個簇當前已有的任務的總能量消耗；?