汪成亮 溫鑫

摘要：

針對智能環(huán)境中基于Rete的規(guī)則推理引擎需要將數(shù)據(jù)集中到sink節(jié)點，導致傳感器網(wǎng)絡中數(shù)據(jù)傳輸量過大的問題，建立了Rete網(wǎng)絡代價模型，并提出了最小傳輸代價的Rete分布的算法（MCoRDS）。該算法通過統(tǒng)計Rete網(wǎng)絡中子模式對事實數(shù)據(jù)的依賴，發(fā)現(xiàn)大部分子模式在對應事實數(shù)據(jù)采集Sensor附近便具備了計算推理條件，故將Rete網(wǎng)絡中的子模式規(guī)則分布到最早匯集其所需所有事實數(shù)據(jù)的Sensor中，即可避免事實數(shù)據(jù)進一步往sink節(jié)點的傳輸，從而大量減少傳感器網(wǎng)絡中的數(shù)據(jù)傳輸量。對比將Rete網(wǎng)絡放置在sink節(jié)點的集中式推理進行了4組仿真實驗。其中第4組實驗，傳感器網(wǎng)絡總跳數(shù)由85000減至8036此處的8063，與圖5中的8036為一致，以哪個為準？另外，減少約90.1%也不準確，是否應該為90.5%？請明確。，減少約90.5%；其余組實驗傳輸跳數(shù)也有一定的減少。實驗結果表明，最小代價的Rete分布具有更小的數(shù)據(jù)傳輸量，在規(guī)則觸發(fā)頻率低、規(guī)則規(guī)模較大的情況下尤甚。

關鍵詞：

智能環(huán)境；規(guī)則推理引擎；傳感網(wǎng)絡；Rete算法；Rete分布

中圖分類號： TP301.6 文獻標志碼：A

0引言

近年來，隨著智能傳感設備的發(fā)展，人們越來越向往智能化的生活環(huán)境。智能環(huán)境[1]是布置了各種傳感器的室內環(huán)境，人們在其中可以進行各種自由交互活動。利用其中遍布的傳感設備，為人們提供各種自動的、智能且高效的服務是該領域的一個研究熱點[2-3]。在智能環(huán)境中智能性的實現(xiàn)通常采用基于規(guī)則的產生式系統(tǒng)[4]，Rete算法[5]是產生式系統(tǒng)中一種高效的模式匹配算法。本文主要研究如何充分利用Rete算法的網(wǎng)絡特性，結合智能環(huán)境中傳感器節(jié)點計算資源不斷加強的趨勢，將Rete推理網(wǎng)絡分布式嵌入到智能環(huán)境中。

傳統(tǒng)的基于規(guī)則的推理引擎將整個推理網(wǎng)絡架設在中心設備，所有無線網(wǎng)絡中的傳感器采集的數(shù)據(jù)都需要往中心設備傳輸，利用智能網(wǎng)關技術實現(xiàn)智能環(huán)境，只能使各節(jié)點僅承擔數(shù)據(jù)采集和通信的功能，這使得無法減少傳感網(wǎng)絡中的數(shù)據(jù)傳輸量，從而導致智能環(huán)境中推理系統(tǒng)實時性差，影響推理響應時間。隨著智能環(huán)境中傳感器節(jié)點的計算與存儲能力的提升，智能環(huán)境中節(jié)點的計算資源利用率過低和網(wǎng)絡中數(shù)據(jù)冗余、傳輸量過大的問題愈加突出。本文通過建立Rete分布傳輸代價模型，按盡早計算的思想，將推理網(wǎng)絡中的計算任務分布式地部署到最靠近參數(shù)采集的傳感器節(jié)點中，讓這些傳感器充分參與到推理計算工作中，減少原始數(shù)據(jù)的轉發(fā)量，從而提高智能環(huán)境的計算資源利用率、降低平均數(shù)據(jù)傳輸量，進而減少服務響應時間，提升系統(tǒng)實時性。

本文的主要工作如下：

1）建立有向圖模型描述Rete推理網(wǎng)絡，建立樹形模型描述智能環(huán)境中的傳感器網(wǎng)絡，在兩者基礎上定義Rete分布方案（Rete Distribution Scheme， RDS），并建立起用傳感器跳數(shù)表示的傳輸代價模型來衡量不同Rete網(wǎng)絡分布方案的優(yōu)劣。

2）根據(jù)早計算，盡量減少智能網(wǎng)絡中的數(shù)據(jù)傳輸量的思想，提出傳輸代價最小的Rete分布方案（Minimum Cost of Rete Distribution Scheme， MCoRDS）。

3）設計仿真實驗對比了集中式Rete分布方案（Center RDS）和分布式Rete分布式方案（Distributed RDS）在傳輸代價上的優(yōu)劣，驗證了利用MCoRDS算法得到的最小代價Rete分布方案（Minimum Cost RDS，MC RDS）的有效性和優(yōu)越性。

1相關研究

1.1智能環(huán)境中傳感網(wǎng)絡

在Sensor網(wǎng)絡中若存在環(huán)路則存在數(shù)據(jù)包永遠在環(huán)路中傳輸?shù)娘L險，進而導致丟失數(shù)據(jù)包，故本文不討論存在環(huán)路的情況，那么可以將其拓撲結構視為森林。智能環(huán)境中通常負責集中處理數(shù)據(jù)的Sink節(jié)點只有一個，故本文將使用樹形拓撲結構描述智能環(huán)境中的傳感網(wǎng)絡[6]。由于各傳感器采集的數(shù)據(jù)最終都會傳輸至Sink節(jié)點，若采用傳統(tǒng)的集中式推理方式，Rete推理引擎全部部署在Sink節(jié)點。這使得傳感器網(wǎng)絡計算資源負載不均且網(wǎng)絡內數(shù)據(jù)傳輸量很大，Sink節(jié)點處可能出現(xiàn)網(wǎng)絡擁塞，系統(tǒng)面臨著響應時間延遲和單點故障引起的系統(tǒng)智能推理癱瘓等問題。

本文希望找到一種有效的Rete推理網(wǎng)絡在傳感器網(wǎng)絡中的分配方案，將Rete網(wǎng)絡中的子模式盡量分離到其他非Sink節(jié)點的傳感器中，這類似于樹型結構計算環(huán)境下的任務調度問題[7-9]。若不考慮Rete網(wǎng)絡中各規(guī)則子模式之間的層次依賴關系，該問題等價于異構樹型多處理器計算平臺下獨立相同任務調度問題，此問題已被證明為Nondeterministic Polynomial（NP）難題[10]。本文充分考慮Rete網(wǎng)絡中各計算模式的層次依賴關系，使用有向圖描述Rete網(wǎng)絡來實現(xiàn)最優(yōu)代價的部署方案。

1.2Rete網(wǎng)絡

由Forgy[5]基于規(guī)則模式匹配所提出的Rete算法解決的是產生式專家系統(tǒng)的規(guī)則匹配效率問題，它主要利用了規(guī)則的時間冗余性和結構相似性。根據(jù)傳統(tǒng)的Rete算法編譯規(guī)則后將得到推理網(wǎng)絡，如圖1所示。Rete網(wǎng)絡分為Alpha網(wǎng)絡和Beta網(wǎng)絡，由4種Rete節(jié)點構成：根節(jié)點Root、Alpha節(jié)點、Beta節(jié)點、規(guī)則激活節(jié)點。

Rete算法主要分為兩個部分，分別是編譯推理網(wǎng)絡和執(zhí)行推理。Rete算法編譯階段是得到Rete推理網(wǎng)絡，執(zhí)行階段則是進行模式匹配的過程。文獻[11]研究過將Rete推理作為一個整體任務，采用現(xiàn)有分布式計算框架在多臺主機上實現(xiàn)匹配推理；但并沒有考慮利用Rete網(wǎng)絡中節(jié)點對事實數(shù)據(jù)的依賴關系，將Rete網(wǎng)絡本身分布式部署到傳感器網(wǎng)絡中，從而未能減少智能環(huán)境中的數(shù)據(jù)傳輸量。本文將著重研究如何將Rete算法編譯得到的推理網(wǎng)絡以合適的方式部署到智能環(huán)境中各個Sensor上，充分利用智能環(huán)境中Sensor的計算和存儲能力，實現(xiàn)實時性更高、安全性更強、傳感器網(wǎng)絡數(shù)據(jù)傳輸量最小的推理執(zhí)行網(wǎng)絡。

2智能環(huán)境下Rete分布及其代價模型

智能環(huán)境中部署Rete網(wǎng)絡分為集中式和分布式兩種方式。采用集中式時，Rete網(wǎng)絡整體將布置在Sink傳感器中；采用分布式時，Rete網(wǎng)絡將以Rete節(jié)點為單位布置到各個相關傳感器，并形成推理網(wǎng)絡。

2.1符號說明

S={s1，s2，…，sm}表示智能環(huán)境中的Sensor集合，m為Sensor數(shù)目。

R={r1，r2，…，rn}表示Rete網(wǎng)絡中Rule集合對應Rule激活節(jié)點，n為規(guī)則數(shù)目。

P={p1，p2，…，pl}表示Rete網(wǎng)絡中事實參數(shù)集合，l為參數(shù)個數(shù)。

Alpha={α1，α2，…，αx}表示Rete網(wǎng)絡中Alpha Node集合，x為Alpha Node數(shù)目。

Beta={β1， β2，…， βy}表示Rete網(wǎng)絡中Beta Node集合，y為Beta Node數(shù)目。

N=Alpha∪Beta表示Rete網(wǎng)絡中所有Rete Node集合，數(shù)目記為z，并有z=x+y成立。

2.2相關定義

定義1Rete網(wǎng)絡。由二元組（N，EN）表示，簡記為Rete，是有向圖，記其平均深度為hr。N為Rete中節(jié)點集合，EN為網(wǎng)絡中邊集。對N中節(jié)點，輸入節(jié)點邊數(shù)為入度，輸出節(jié)點邊數(shù)為出度，Beta節(jié)點入度大于2。

定義2Sensor網(wǎng)絡。由二元組（S，ES）表示，簡記為Gs，拓撲結構為樹，記其平均深度為hs。S為Gs中Sensor集合，ES為S中Sensor存在連接的邊集。

定義3Rete分布。Rete網(wǎng)絡在Sensor網(wǎng)絡中的分配方案，簡記為RDS。傳統(tǒng)集中式的Rete推理系統(tǒng)是將Rete網(wǎng)絡全部分配到Sensor網(wǎng)絡中的Sink節(jié)點中，稱這種特殊的分布為Center RDS，則其他分布稱為Distributed RDS。

定義4Rete分布代價為在每個事實數(shù)據(jù)產生周期內從事實數(shù)據(jù)產生開始到Rete推理結束期間整個網(wǎng)絡中所有數(shù)據(jù)的傳輸代價（簡記為Ctran）和推理計算代價（簡記為Ccalc）之和，記作C。

2.3分布代價模型

根據(jù)上述定義，有式（1）成立：

C=Ctran+Ccalc（1）

本文的核心問題即是找到一種RDS使得式（1）盡可能小，稱這種分布為最小傳輸代價Rete分布方案（Minimum Cost Rete Distribution Scheme， MC RDS）。在智能環(huán)境下，Sensor網(wǎng)絡中Sensor的通信能耗最大，而感知、計算的能耗較小，基本可以忽略，所以使Sensor網(wǎng)絡中的數(shù)據(jù)傳輸量盡量小是傳感網(wǎng)絡領域的普遍追求。由于Rete網(wǎng)絡中Rete Node有層次依賴關系，包括了智能環(huán)境中Rete推理所產生的所有傳輸代價以下過程這句話不太通順，請作相應調整。智能環(huán)境中Rete推理產生的所有傳輸包括了以下過程，傳感器采集到的事實數(shù)據(jù)從Rete網(wǎng)絡Alpha Node進入Rete推理網(wǎng)絡，Rete網(wǎng)絡得到事實數(shù)據(jù)后，根據(jù)Rete網(wǎng)絡中的層次流向關系，將Rete Node計算結果為True的結果往深層網(wǎng)絡傳輸，直到第一個計算結果為False的Rete Node或者是抵達Rule激活節(jié)點結束。使用C（pi，αi）表示產生事實參數(shù)pi所在Sensor到Alpha Node αi所在Sensor所需傳輸代價；Cej為Rete網(wǎng)絡中第j條邊兩端Rete Node所在Sensor之間的傳輸代價。假設相鄰Sensor間只需一跳的傳輸代價相同，記為單位1這是什么意思？表達是否正確？回復：表達的意思是，本文將Sensor間一跳路由的傳輸代價記為1，則式（1）可以轉化為式（2）：

其中：∑C（pi，αi）為所有參數(shù)傳輸?shù)较鄳腁lpha Node傳輸代價總和；∑Cej代表Rete網(wǎng)絡中所有邊所產生的傳輸代價的總和。Alpha Node一般是系統(tǒng)單個屬性的測試，只包含一個事實參數(shù)，故有l(wèi)=x。對上述任意傳輸代價C（pi，αi）或Cej，按EN中邊兩端的Rete Node是否在同一Sensor可分為兩種情形，在同一Sensor時（如圖3在正文中，圖形編號的順序是依次出現(xiàn)，本文先出現(xiàn)圖3，后出現(xiàn)圖2，順序不對，需要調整圖形，或者調整相關引用語句。建議調整此段的描述語句，是否可以刪除引用圖3的相應語句。中實線有向邊）傳輸代價為0；在不同Sensor（如圖3中虛線有向邊）傳輸代價為兩端Sensor間跳數(shù)。

從Rete網(wǎng)絡最終是否觸發(fā)規(guī)則的角度上來說，事實數(shù)據(jù)分兩種情況：一種是不觸發(fā)規(guī)則的數(shù)據(jù)，此時Rete推理結果將只到達某些中間Rete Node便停止往下傳輸結果，∑Cej中只包含以上產生傳輸?shù)膃j；此時應將Rete Node分配在能早得到數(shù)據(jù)的Sensor中，越早越好，這樣可以避免大量的不必要的傳輸。另一種是觸發(fā)規(guī)則的數(shù)據(jù)，此時事實數(shù)據(jù)將最終觸發(fā)結果到Rule激發(fā)節(jié)點，∑Cej包含Rete網(wǎng)絡中EN，此時若將Rule激發(fā)節(jié)點盡可能地分布在能早計算出該Rule的Sensor中，也將減少一些傳輸代價。

3最小代價的Rete分布

為找到使得傳輸代價C盡量小的RDS，本文首先Center RDS這一特別的Rete分布本文首先針對Center RDS這一特別的Rete分布此處語句不通順，請作相應調整。，分析其傳輸代價，然后嘗試通過將某些Rete Node逐步分配到其他傳感器來減少Rete推理過程中所產生的傳輸代價，從而得到更優(yōu)秀的Rete分布。集中式Rete分布如圖2所示。

由于所有Rete Node都在Sink節(jié)點內，∑Cej=0。此時公式轉化為C=∑C（pi，αi），即所有事實參數(shù)傳輸?shù)絊ink節(jié)點所需傳輸代價。為分析出MC RDS，首先，嘗試將Alpha Node分配到Sink節(jié)點以外的節(jié)點，比較前后傳輸代價的變化，可以猜想：將Rete網(wǎng)絡中每個Rete Node移動至剛好能提供其所有輸入所需事實參數(shù)的Sensor上，將得到最小傳輸代價的Rete分布；然后，將上述猜想作為假設條件，分析證明所有符合條件的后續(xù)Rete Node前移將得到更小的Rete分布；最后，得到MC RDS算法及偽碼描述，并進行算法復雜度分析。

由于本文假設Sensor網(wǎng)絡是樹形拓撲結構，為方便算法思想描述，現(xiàn)對Rete Node從集中式全部分配在Sink節(jié)點上轉化成Rete Node分配到其他Sensor的過程進行如下定義。

定義5Sink節(jié)點是樹形網(wǎng)絡的根節(jié)點，所有其他Sensor都與Sink節(jié)點有親緣關系。將Rete Node從分配在Sink節(jié)點轉變?yōu)榉峙涞狡渌鸖ensor的過程稱為Rete Node移出（moving out）。

定義6將Rete Node從分配在接近Sink節(jié)點的祖先Sensor中轉變?yōu)榉峙湓谶h離Sink節(jié)點的子孫Sensor的過程稱為Rete Node前移（moving forward）。

定義7Rete網(wǎng)絡在sensor節(jié)點間傳輸數(shù)據(jù)所需路由跳數(shù)記為T，用來衡量傳輸代價。如從si傳輸?shù)絪j的傳輸跳數(shù)即為T（si，sj）。

3.1Alpha Node移出

顯然Alpha Node應該移動到對應的測試事實參數(shù)傳輸路線所在Sensor處。比如圖2中α6，應分配到s9 → s8 → s5路徑的Sensor上，針對p6不同觸發(fā)情況如下所示。

1）對于不觸發(fā)規(guī)則的情況，設此時α6分配在si上，則C（p6，α6）=T（s5，si），由于p6不觸發(fā)規(guī)則，到達α6所在si后推理得到結果為false，將不再往下層Rete Node傳輸結果，此時C（α6， β5）=0，C（α6，γ5）=0。故只需考慮p6傳輸?shù)溅?所在Sensor上所需傳輸代價C（p6，α6），越小越好，即si離s5越近越好。顯然此時將α6分配在p6所在s5上最近，C（p6 ，α6 ） = T（s5 ，s5 ） = 0最小。

2）對于觸發(fā)規(guī)則的情況，α6所需輸入為p6，需要向β5、γ5輸出。由于β5、γ5都在Sink節(jié)點上，α6的后續(xù)結果只需往Sink節(jié)點傳輸一份（見圖3中α6出發(fā)的粗有向虛線），在所有數(shù)據(jù)一次傳輸所需的傳輸代價都相同的假設條件下，無論α6分配在p6傳輸?shù)絊ink路線上的任何Sensor上，傳輸代價都不會發(fā)生變化。故此時將α6分配在p6所在s5上，C（α6， β5）=C（α6，r5）=T（s5，s9）=2也是最小傳輸代價的Rete分布。

由上述嘗試Alpha Node移出Sink節(jié)點的分析，本文提出將Rete網(wǎng)絡中每個Rete Node前移至剛好能提供其所有輸入所需事實參數(shù)的Sensor上，將得到最小傳輸代價的Rete分布的猜想。

3.2其他Rete Node前移

然后，考慮其他Rete Node移出Sink節(jié)點。假設當前Rete Node所需的上層輸入Rete Node已經前移至剛好能提供其所有輸入所需事實參數(shù)的Sensor上，并且記作n，設入度為a，出度為b，那么對n移出Sink節(jié)點必然沿提供全參數(shù)輸入的路線前移。此時，也可以分不觸發(fā)規(guī)則和觸發(fā)規(guī)則兩種情況進行討論，如圖3所示。

在觸發(fā)規(guī)則情況下，為避免向其他分支傳輸額外的數(shù)據(jù)導致額外的輸出代價，n也應該分配到提供全參數(shù)輸入的路線上。假設n分配在si上，由于計算結果將觸發(fā)規(guī)則，則n分配，影響計算n所需其他Sensor向si傳輸數(shù)據(jù)的代價，還對計算完n后需要將結果傳輸?shù)胶罄m(xù)Rete Node所在Sensor的傳輸代價。此時n每前移一跳傳感器，則所需的輸入?yún)?shù)的傳輸代價將減少a跳；同時，n的結果數(shù)據(jù)往后續(xù)Rete Node傳輸代價將增加b跳。由于在樹形傳感網(wǎng)絡中，需要n的結果數(shù)據(jù)的后續(xù)Rete Node都在一條Sensor路線上，往后續(xù)Rete Node所在Sensor只需傳輸一份數(shù)據(jù)（見圖3中粗有向虛線）。故實際上n每前移一跳傳感器，n的結果數(shù)據(jù)往后續(xù)Rete Node傳輸代價只增加1跳。

綜上所述，從集中式Rete分布出發(fā)，將任何一個Rete Node向符合條件的傳感器前移一跳，其所代表的子模式將早一跳得到結果，若結果為false，則提前一跳避免大量后續(xù)數(shù)據(jù)傳輸；否則，由于在樹形Sensor網(wǎng)絡中后續(xù)傳輸只需要傳輸一份拷貝，這相當于用多一跳的后續(xù)結果傳輸來減少每一個上層Rete Node到該Rete Node的一跳數(shù)據(jù)傳輸。故將Rete網(wǎng)絡中每個Rete Node前移至剛好能提供其所有輸入所需事實參數(shù)的Sensor上，將得到最小傳輸代價的Rete分布。

3.3最小傳輸代價Rete分布算法

根據(jù)盡早計算思想，本文提出最小傳輸代價Rete分布算法（MCoRDS）。該算法分為3個步驟：1）初始化Rete分布為集中式分布方式，即將所有Rete Node分配在Sink傳感器中。2）調用參數(shù)統(tǒng)計算法（GetNodeParaList），采用后續(xù)遍歷方式統(tǒng)計樹形傳感器網(wǎng)絡中各傳感器所能獲得的參數(shù)列表。3）遍歷Rete中所有Node，根據(jù)GetNodeParaList中得到的傳感器參數(shù)列表按照Rete Node移出的方式移致合適的Sensor。

經過上述3個步驟得到的結果即為傳輸代價最小的Rete分布，以上兩個算法的偽碼描述如下。

算法1MCoRDS。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：Rete Net Directed Graph Rete； Sensor Net Gs；Rete Node Set N；Sensor Node Set S。

輸出：Rete Distribution Scheme RDSS。

初始化：s=NULL；//Initialization of current Sensor pointer；

1）

For ReteNode n in RDSS

2）

n.Sensor=Sink；//initialize to center scheme

3）

Sink.paraList=GetNodeParaList（Gs）；//call CountNodeParaList

4）

for ReteNode n in RDSS

5）

s=n.Sensor；

6）

while s.hasNextChild//find out next Sensor to moving forward

7）

if n.paraList s.paraList//s is the available Sensor for n

8）

n.Sensor=s；

9）

s=s.nextChild；

10）

end if

11）

end while

12）

end for

13）

return RDSS；

程序后

算法2GetNodeParaList。

有序號的程序——————————Shift+Alt+Y

程序前

輸入：parameter set Para； Sensor Net Gs；Sensor Node Set S。

輸出：the paraList of Sensor。

Initialization： s=Gs.root；//initial s as root node of Sensor net

1）

for para p in Para

2）

Para.Sensor.paraList.add（p）；//add original parameters to paralist of Sensor

3）

end for

4）

while s.hasNextChild

5）

s.paraList.add（CountNodeParaList（s.nextChild））；//visit the prelist of Sensor net by posttraversing

6）

end while

7）

return Gs.paraList；

程序后

算法2 GetNodeParaList有兩部分操作。第一部分為第1）行至第3）行的for循環(huán)，遍歷Para為傳感器網(wǎng)絡中Sensor初始化paraList，復雜度為Θ（l）復雜度的符號表示為“Θ”，不是“O”嗎？表述是否正確？請明確。

回復：在算法復雜度的表示中，Θ為精確界，O為上界，文中的復雜度是精確的，當然也可以使用O，如果需要就使用O吧，其中l(wèi)是Para個數(shù)；第二部分為第4）行至第6）行的while循環(huán)，采用后續(xù)遍歷的方法將位于樹形傳感網(wǎng)絡葉子節(jié)點Sensor中的Para傳輸至后續(xù)Sensor中，從而統(tǒng)計出Sensor節(jié)點集S中各傳感器對應的paraList，復雜度為Θ（m），其中m為Sensor數(shù)目。故算法2的復雜度為max（Θ（m），Θ（l））。

算法1 MCoRDS主要耗時操作為第4）行到第12）行的for循環(huán)和while循環(huán)，第6）行到第11）行的內層while循環(huán)在樹形傳感網(wǎng)絡深度上嘗試前移Rete Node，并最終將Rete Node前移至剛好能夠獲取其所需所有參數(shù)的傳感器中，第4）行至第12）行的外層for循環(huán)則是遍歷所有的Rete Node，故其時間復雜度與Rete Node數(shù)目以及樹形傳感器網(wǎng)絡深度的乘積線性相關，即Θ（（p+q）*log m），其中：p為Alpha Node數(shù)目，q為Beta Node數(shù)目。

4仿真實驗

仿真實驗目的是在控制智能環(huán)境中的傳感器網(wǎng)絡、Rete推理網(wǎng)絡、推理時間周期、事實數(shù)據(jù)發(fā)生頻率四個條件相同，只允許規(guī)則觸發(fā)頻率不同的情況下，對比Center DS和MC DS下的推理過程中所需的數(shù)據(jù)傳輸量的區(qū)別來驗證MCoRDS，數(shù)據(jù)傳輸量以計算網(wǎng)絡內傳輸跳數(shù)總和反映[12]。本文使用Smart Environment Simulator Tool[13]模擬智能環(huán)境下的傳感器網(wǎng)絡，并在此平臺上增加了可以按照一定數(shù)據(jù)發(fā)生頻率和規(guī)則觸發(fā)率的數(shù)據(jù)模擬長生事實數(shù)據(jù)的數(shù)據(jù)發(fā)生模塊。

為驗證MCoRDS的有效性，選取了4組Rete網(wǎng)絡和Sensor網(wǎng)絡對，實驗編號及其各項指標如表1所示。

為保證數(shù)據(jù)量，本文將統(tǒng)計周期設置為1s，數(shù)據(jù)發(fā)生頻率為50Hz，即將在智能環(huán)境中1s內產生50次原始事實數(shù)據(jù)，并模擬它們分別在Center RDS和使用MCoRDS算法得到的MC RDS下的路由傳輸跳數(shù)。由于Rete網(wǎng)絡中數(shù)據(jù)傳輸量與規(guī)則觸發(fā)與否有很大的關系，本文分別以0Hz、10Hz、30Hz、50Hz四組規(guī)則觸發(fā)頻率隨機模擬發(fā)生事實數(shù)據(jù)，并統(tǒng)計了上述四組實驗在個規(guī)則觸發(fā)頻率下所產生的數(shù)據(jù)傳輸跳數(shù)，相應內容如表2。

4.1規(guī)則觸發(fā)情況對不同分布方式的傳輸量影響分析

根據(jù)表2可以看出，對相同編號的實驗，在統(tǒng)計周期、不同規(guī)則觸發(fā)頻率下，Center RDS網(wǎng)絡內產生的數(shù)據(jù)跳數(shù)總和是固定值；對于MC RDS，隨著規(guī)則觸發(fā)頻率的降低，其在統(tǒng)計周期中產生的數(shù)據(jù)跳數(shù)總和將不斷減少。

產生以上現(xiàn)象的原因是在Center RDS中所有Rete Node都部署在Sink節(jié)點，傳感網(wǎng)絡中其他傳感器采集的數(shù)據(jù)將全部傳輸至Sink節(jié)點，再由Sink節(jié)點推理出相應結果，其數(shù)據(jù)傳輸量應該等于所有參數(shù)所在Sensor到Sink節(jié)點的跳數(shù)之和，為固定值。而在MC RDS中，由于計算Rete Node靠近相關參數(shù)采集的傳感器，原始模擬數(shù)據(jù)到達Rete Node所在節(jié)點，若該模式不觸發(fā)，則不再往后續(xù)傳感器產生數(shù)據(jù)傳輸，故此時規(guī)則觸發(fā)頻率越低，傳輸?shù)皆礁邔觽鞲衅鞯臄?shù)據(jù)越少，數(shù)據(jù)傳輸跳數(shù)也將減少得越多。在現(xiàn)實應用場景中，通常規(guī)則觸發(fā)率也比較低，這表明通過MC RDS的可行性和高效性。

4.2兩種特殊規(guī)則觸發(fā)頻率下數(shù)據(jù)傳輸量分析

在本文采用的四種規(guī)則觸發(fā)頻率下，0Hz與50Hz是兩種特殊的規(guī)則觸發(fā)頻率，0Hz代表著在統(tǒng)計周期內產生的50次模擬數(shù)據(jù)都不會到達最終的規(guī)則激活節(jié)點，50Hz則代表產生的50次模擬數(shù)據(jù)最終全部都會到達最終的規(guī)則激活節(jié)點。

以實驗編號為橫坐標，將0Hz規(guī)則觸發(fā)頻率下兩種Rete分布方式下的數(shù)據(jù)傳輸量繪制到圖5。在所有采集參數(shù)都不會到達最終的規(guī)則激活節(jié)點這種特殊的數(shù)據(jù)設置下，通過實驗數(shù)據(jù)可以看到Center RDS中，數(shù)據(jù)傳輸量一直維持在很高的水平，并且與Rete網(wǎng)絡和Sensor網(wǎng)絡的規(guī)模呈正相關的提升；在MC RDS中，數(shù)據(jù)傳輸量始終遠低于相應Center RDS中數(shù)據(jù)傳輸量，且傳輸跳數(shù)隨Rete網(wǎng)絡和Sensor網(wǎng)絡的規(guī)模變大的過程中增加的劇烈程度要遠低于Center RDS。

同時，以實驗編號為橫坐標，將50Hz規(guī)則觸發(fā)頻率下兩種Rete分布方式下的數(shù)據(jù)傳輸量繪制到圖6。在所有采集參數(shù)都會到達最終的規(guī)則激活節(jié)點這種特殊的數(shù)據(jù)設置下，隨著Rete網(wǎng)絡和Sensor網(wǎng)絡的規(guī)模變大的過程中，MC RDS和Center RDS中的數(shù)據(jù)傳輸跳數(shù)都將快速地增加，但是MC RDS的數(shù)據(jù)傳輸跳數(shù)總和相對Center RDS仍然有一定程度的減少。

以上結果充分驗證了最小傳輸代價下的Rete分布MC RDS的有效性，尤其是在規(guī)則觸發(fā)頻率較低的真實環(huán)境中更加有效。

5結語

針對傳統(tǒng)的集中式推理網(wǎng)絡在傳感器網(wǎng)絡間造成數(shù)據(jù)傳輸量大、并導致系統(tǒng)響應時間不夠快、各傳感器綜合計算資源利用率低的問題，通過嘗試將Sink節(jié)點中的Rete Node盡可能前移的思路，本文提出了MCoRDS算法。利用該算法，給定一個Rete網(wǎng)絡可以得到在當前智能環(huán)境下的最小傳輸代價下的Rete分布。仿真實驗表明，相比傳統(tǒng)的集中式推理方式，按照該分布方式部署Rete網(wǎng)絡到智能環(huán)境中，在規(guī)則觸發(fā)頻率較低的應用場景下，將大量地減少傳感網(wǎng)絡中的數(shù)據(jù)傳輸量，在規(guī)則觸發(fā)頻率不低的情況下，傳感網(wǎng)絡中的數(shù)據(jù)傳輸量也將得到有效的降低。由于描述Rete網(wǎng)絡和Sensor網(wǎng)絡的規(guī)模比較復雜，考慮到實際應用環(huán)境一般情況下的特點，本文在設計四組驗證實驗時，Rete網(wǎng)絡和Sensor網(wǎng)絡規(guī)模作為一個整體，在擴大規(guī)模時，同時擴大了兩者的規(guī)模，并沒有考察Rete網(wǎng)絡和Sensor網(wǎng)絡規(guī)模各自對實驗的影響，這是后續(xù)研究值得關注的方向。

參考文獻：

[1]

HUTTON D M. Smart environments： technology， protocols and applications [J]. Kybernetes， 1972， 4（4）：903-904.

[2]

BERNINI D， FIAMBERTI F， MICUCCI D， et al. Architectural abstractions for spacesbased communication in smart environments [J]. Journal of Ambient Intelligence and Smart Environments， 2012， 4（3）： 253-277.

[3]

RASHIDI P， COOK D J， HOLDER L B， et al. Discovering activities to recognize and track in a smart environment [J]. IEEE Transactions on Knowledge and Data Engineering， 2011， 23（4）： 527-539.

[4]

KAWAKAMI T， FUJITA N， YOSHIHISA T， et al. An evaluation and implementation of rulebased home energy management system using the Rete algorithm [J]. The Scientific World Journal， 2014， 2014： 591478.

[5]

FORGY C L. Rete： a fast algorithm for the many pattern/many object pattern match problem [J]. Artificial Intelligence， 1982， 19（1）： 17-37.

[6]

DING M， CHENG X， XUE G. Aggregation tree construction in sensor networks [C]// Proceedings of the 2003 IEEE 58th Vehicular Technology Conference on VTC 2003Fall. Piscataway， NJ： IEEE， 2003， 4： 2168-2172.

[7]

VEERAVALLI B， YAO J. Divisible load scheduling strategies on distributed multilevel tree networks with communication delays and buffer constraints [J]. Computer Communications， 2004， 27（1）： 93-110.

[8]

BEAUMONT O， CASANOVA H， LEGRAND A， et al. Scheduling divisible loads on star and tree networks： results and open problems [J]. IEEE Transactions on Parallel & Distributed Systems， 2005， 16（3）： 207-218.

[9]

BANINO C， BEAUMONT O， CARTER L， et al. Scheduling strategies for masterslave tasking on heterogeneous processor platforms [J]. IEEE Transactions on Parallel & Distributed Systems， 2004， 15（4）： 319-330.

[10]

DUTOT P F. Complexity of masterslave tasking on heterogeneous trees [J]. European Journal of Operational Research， 2005， 164（3）： 690-695.

[11]

張琦.基于MapReduce的分布式規(guī)則匹配系統(tǒng)的研究與實現(xiàn)[D].杭州，浙江大學，2011：1-71.（ZHANG Q. The research and implementation of MapReducebased distributed rule matching system [D]. Hangzhou： Zhejiang University， 2011： 1-71.）

[12]

YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey [J]. Computer Networks， 2008， 52（12）： 2292-2330.

[13]

WANG C， DE D， SONG W Z. Trajectory mining from anonymous binary motion Sensors in smart environment [J]. KnowledgeBased Systems， 2013， 37： 346-356.