汪成亮 溫鑫

摘要：

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

關(guān)鍵詞：

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

中圖分類號(hào)： TP301.6 文獻(xiàn)標(biāo)志碼：A

0引言

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

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

本文的主要工作如下：

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

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

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

1相關(guān)研究

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

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

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

1.2Rete網(wǎng)絡(luò)

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

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

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

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

2.1符號(hào)說(shuō)明

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

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

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

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

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

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

2.2相關(guān)定義

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

定義2Sensor網(wǎng)絡(luò)。由二元組（S，ES）表示，簡(jiǎn)記為Gs，拓?fù)浣Y(jié)構(gòu)為樹(shù)，記其平均深度為hs。S為Gs中Sensor集合，ES為S中Sensor存在連接的邊集。

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

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

2.3分布代價(jià)模型

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

C=Ctran+Ccalc（1）

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

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

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

3最小代價(jià)的Rete分布

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

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

由于本文假設(shè)Sensor網(wǎng)絡(luò)是樹(shù)形拓?fù)浣Y(jié)構(gòu)，為方便算法思想描述，現(xiàn)對(duì)Rete Node從集中式全部分配在Sink節(jié)點(diǎn)上轉(zhuǎn)化成Rete Node分配到其他Sensor的過(guò)程進(jìn)行如下定義。

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

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

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

3.1Alpha Node移出

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

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

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

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

3.2其他Rete Node前移

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

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

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

3.3最小傳輸代價(jià)Rete分布算法

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

經(jīng)過(guò)上述3個(gè)步驟得到的結(jié)果即為傳輸代價(jià)最小的Rete分布，以上兩個(gè)算法的偽碼描述如下。

算法1MCoRDS。

有序號(hào)的程序——————————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。

有序號(hào)的程序——————————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)絡(luò)中Sensor初始化paraList，復(fù)雜度為Θ（l）復(fù)雜度的符號(hào)表示為“Θ”，不是“O”嗎？表述是否正確？請(qǐng)明確。

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

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

4仿真實(shí)驗(yàn)

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

為驗(yàn)證MCoRDS的有效性，選取了4組Rete網(wǎng)絡(luò)和Sensor網(wǎng)絡(luò)對(duì)，實(shí)驗(yàn)編號(hào)及其各項(xiàng)指標(biāo)如表1所示。

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

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

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

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

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

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

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

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

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

5結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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)的研究與實(shí)現(xiàn)[D].杭州，浙江大學(xué)，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.