[發明專利]一種基于實測帶寬的多智能體互聯網數據采集任務分配方法

有效

• 申請號: 201710052671.6
• 申請日: 2017-01-24
• 公開（公告）號: CN106886459B
• 公開（公告）日: 2019-07-23
• 發明（設計）人: 沈頌
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48;G06F16/951
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 劉靜;邱啟旺

1.一種基于實測帶寬的多智能體互聯網數據采集任務分配方法，其特征在于：假定在環境中存在L個目標任務T₁，T₂，…,T_L和K個智能體節點A₁,A₂,…,A_K，若K>L，則執行單任務分配方法；否則執行多任務分配方法；

所述的單任務分配方法步驟如下：

a.針對每個智能體節點A_i與任務T_j，計算區域判決指標c_ij＝(任務數+1)/(B_C+B_S)，找出區域判決指標計算結果最小的節點；

B_C表示任務的目標區域與智能體所在區域的匹配度，計算方法如下：由智能體在建立種子信息表時先行從該種子頁面爬取根頁面三次，通過(爬取位數)/(爬取所消耗的時間)獲取爬行帶寬，存入種子庫中相應B_C字段；

B_S表示存儲區域與智能體所在區域的匹配度，計算方法如下：由智能體在建立種子信息表時先行將一個標準100KB文件存入存儲區域三次，通過(存取位數)/(存取所消耗的時間)獲取存儲帶寬，存入種子庫中相應B_S字段；

b.將待分配的任務分配給步驟(1)計算得到的節點；

所述的多任務分配方法步驟如下：

(1)在所有任務中每次分配K項，直到剩余任務數小于K；剩余任務可以在任務數增加后再行分配，也可以以單任務方式分配；

(2)已知智能體A_i完成目標任務T_j的代價矩陣為C＝(c_ij)，其中c_ij的計算方法與單任務時相同；其中i＝1,2,…,K，j＝1,2,…,K；

(3)將(c_ij)的每行元素都減去該行的最小元素，再將所得新系數矩陣的每列元素中減去該列的最小元素，獲得等價代價矩陣C’＝(c'_ij)；

(4)作最少的直線覆蓋所有0元素，通過找0元素進行試分配；方法是：先按照行或列找有沒有可以覆蓋K個元素的直線，若有則作該直線，若沒有則再找有沒有可以覆蓋K-1個元素的直線并作該直線，依此方法進行下去，直到所有0元素被覆蓋；若這樣能找出不同行不同列的K個0元素，轉步驟(6)，否則轉步驟(5)；

(5)調整代價矩陣C’，在未被直線穿過的數集中，找出最小的數z，讓該數集對應的所有行中的所有數減去z，而讓所有被直線穿過的列中的數加上z，以保證系數矩陣中不出現負元素，得到新系數矩陣；新系數矩陣的最優解和原問題相同，此時去掉直線，用新系數矩陣代替C’，返回步驟(3)；

(6)以這K個獨立0元素對應解矩陣(c'_ij)中的元素為1，其余為0，得到最優解矩陣(c”_ij)，即此時矩陣元素中c”_ij＝1所代表的結果是智能體i被分配了任務j，其中i,j＝1,2,…,K。