[發(fā)明專利]基于任務(wù)分解的分布式RFID復(fù)雜事件檢測方法

有效

• 申請?zhí)枺?/td>: 201110332235.7
• 申請日: 2011-10-27
• 公開（公告）號: CN102508640A
• 公開（公告）日: 2012-06-20
• 發(fā)明（設(shè)計）人: 李戰(zhàn)懷;陳群;孫林超;金健;陳琳;康莊莊;劉海龍;潘巍;彭商濂;聶炎明;李強;謝芳全;劉敏
• 申請（專利權(quán)）人: 西北工業(yè)大學(xué)
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 西北工業(yè)大學(xué)專利中心 61204
• 代理人: 顧潮琪

1.一種基于任務(wù)分解的分布式RFID復(fù)雜事件檢測方法，其特征在于包括下述步驟：

第一步，將復(fù)雜任務(wù)分解為一組滿足處理節(jié)點負載限制的子任務(wù)，并將所有子任務(wù)組織成一棵任務(wù)樹；

本發(fā)明采取一種迭代策略分解復(fù)雜任務(wù)和構(gòu)造任務(wù)樹，具體步驟如下：

1)針對給定處理節(jié)點的負載上限r(nóng)ateT從候選事件流中選擇若干個流，連同它們間的約束條件作為子任務(wù)；

2)從候選集中刪除被選中的事件流，并判斷候選集是否為空，如果為空，則迭代結(jié)束；否則執(zhí)行步驟3)；

3)將子任務(wù)檢測輸出的中間結(jié)果定義為虛事件流，計算子任務(wù)檢測輸出的虛事件流的速率以及它與候選集中剩余事件流間匹配率，并將虛事件流加入候選集；然后轉(zhuǎn)到步驟1)，開始針對另一個處理節(jié)點新一輪處理；

第二步，采用基于位圖索引的復(fù)雜事件檢測算法處理子任務(wù)，設(shè)子任務(wù)包含P個輸入事件流，則具體檢測過稱包含以下步驟：

1)創(chuàng)建P個B+樹作為輸入事件流的緩沖容器；按匹配率升序為不同事件流的事件實體指定查找順序；

2)每個事件實體e到來時觸發(fā)一次檢測動作，包括以下內(nèi)容：

a)為e建立P位位圖，將其所屬事件流的編號對應(yīng)的那一位置1；

b)按查找順序在緩沖容器中查找匹配的事件實體，針對任一容器，在該容器中查找與e匹配的事件實體，如果找到，執(zhí)行步驟c)，否則執(zhí)行步驟d)；

c)合并e和與之相匹配事件實體的位圖，并以合并結(jié)果更新它們各自的位圖，然后在這兩個事件實體之間建立指針，判斷合并后位圖的所有位是否均為1，如果是，則表示檢測到一組結(jié)果，輸出結(jié)果，執(zhí)行步驟d)；否則轉(zhuǎn)到步驟b)，在下一容器中進行查找；

d)將事件e連同其位圖插入對應(yīng)的容器，結(jié)束本次檢測，等待新事件實體；3)從緩沖容器中刪除過期事件實體及其位圖，并將與該事件實體匹配的未過期事件實體的位圖的相應(yīng)位置0。

2.根據(jù)權(quán)利要求1所述的基于任務(wù)分解的分布式RFID復(fù)雜事件檢測方法，其特征在于：所述的第一步步驟1)第一次迭代時候選事件流為復(fù)雜任務(wù)中的原子事件流。

3.根據(jù)權(quán)利要求1所述的基于任務(wù)分解的分布式RFID復(fù)雜事件檢測方法，其特征在于：所述的第一步步驟1)以N表示候選事件流的個數(shù)，以m(i，j)表示節(jié)點負載上限為j，候選事件流為[1-i]時可得到的最大壓縮比；N維向量X表示選擇方案，X的第i位為1表示候選事件流i被選中，為0表示沒有被選中，X(i，j)表示與M(i，j)建立對應(yīng)的選擇向量，選擇事件流的方法包括以下步驟：

a)對rateT和各候選事件流的速率rate_i，進行等比例放縮和四舍五入處理變成整數(shù)，舍入誤差控制在5％以內(nèi)，i表示候選事件流編號，rate_i表示編號為i的候選數(shù)據(jù)流的速率；

b)對編號為1的候選事件流，以j表示處理節(jié)點的負載能力，考察從1到rateT的每個j：當j＜rate₁時，置m(1，j)＝0，X(1，j)的第1位為0；當j≥rate₁時，置m(1，j)＝1，X(1，j)的第1位為1；

c)對編號為i的候選事件流，如果i＞N，則轉(zhuǎn)到步驟f)；否則對i考察從1到rateT的每個j：當j＜rate_i時，置m(i，j)＝m(i-1，j)，X(i，j)＝X(i-1，j)；當j≥rate_i時轉(zhuǎn)到步驟d)；

d)在選擇方案X(i，j-rate_i)中加入第i個候選事件流，并計算其壓縮比compratio，然后比較compratio與m(i-1，j)的大小：如果compratio大，則m[i][j]＝compratio，置X(i，j)＝X(i-1，j-rate_i)，X(i，j)第i位為1，否則置z[i][j]＝m[i-1][j]，X(i，j)＝X(i-1，j)；

e)對事件流i考察完所有的j后，考察事件流i+1，把j置0，轉(zhuǎn)到步驟c)；

f)選擇過程結(jié)束，向量X(N，rateT)即為選擇方案，相應(yīng)的壓縮比為m(N，rateT)。