戰(zhàn)場信息分發(fā)系統(tǒng)中的高效模糊匹配算法

劉曉宏，雷偉斌，劉國永，孫 娟，左欽文

（1.國營第七八五廠，太原 030024；2.北方自動控制技術(shù)研究所，太原 030006；3.軍事科學(xué)院防化研究院，北京 102205）

0 引言

發(fā)布/訂閱系統(tǒng)是一種使信息生產(chǎn)者和信息消費(fèi)者以匿名方式進(jìn)行交互的中間系統(tǒng)?；趦?nèi)容的發(fā)布/訂閱模式，與基于主題的發(fā)布/訂閱模式相比，擁有更強(qiáng)的信息需求表達(dá)能力，因此，可以為戰(zhàn)場信息分發(fā)系統(tǒng)提供更為精準(zhǔn)和高效的信息共享能力。事件與訂閱的匹配算法是基于內(nèi)容的發(fā)布/訂閱系統(tǒng)中重要的研究內(nèi)容之一。事件的匹配效率，不僅決定了系統(tǒng)的實(shí)時(shí)性是否能夠得到滿足，還制約著整個(gè)系統(tǒng)的可擴(kuò)展性［1］，因此，也決定了基于內(nèi)容的發(fā)布/訂閱模式在戰(zhàn)場信息分發(fā)系統(tǒng)中應(yīng)用的可行性。目前，事件與訂閱的高效精確匹配算法已有較多的研究成果［1-3］，但均未考慮用戶信息需求與訂閱的模糊性問題，因此，并不適合直接應(yīng)用于戰(zhàn)場信息分發(fā)系統(tǒng)中。文獻(xiàn)［4］研究了在固定的樹形拓?fù)渚W(wǎng)絡(luò)中，如何利用訂閱約束間的邏輯覆蓋關(guān)系來減少訂閱的轉(zhuǎn)發(fā)數(shù)量并降低路由節(jié)點(diǎn)中維護(hù)的訂閱數(shù)據(jù)的規(guī)模，但該方法無法適用于戰(zhàn)場上動態(tài)的無線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

本文結(jié)合戰(zhàn)場應(yīng)用環(huán)境的特點(diǎn)，對基于內(nèi)容的戰(zhàn)場信息分發(fā)系統(tǒng)中的高效模糊匹配算法進(jìn)行研究，充分考慮戰(zhàn)場上作戰(zhàn)用戶對信息需求認(rèn)識與表達(dá)的主觀性和模糊性［5］，將模糊集合理論應(yīng)用于戰(zhàn)場信息與用戶訂閱信息的匹配過程中，以提高匹配結(jié)果的合理性，從而保證戰(zhàn)場信息分發(fā)共享的合理性，并對提高模糊匹配算法效率，降低訂閱信息維護(hù)成本的方法進(jìn)行研究，提出一種訂閱信息的高效組織模式，即分段完全邏輯覆蓋模式，并通過仿真實(shí)驗(yàn)對其效率進(jìn)行驗(yàn)證。

1 基于內(nèi)容的戰(zhàn)場信息分發(fā)系統(tǒng)

1.1 戰(zhàn)場信息分發(fā)系統(tǒng)的概念

以基于內(nèi)容的發(fā)布/訂閱技術(shù)為基礎(chǔ)的戰(zhàn)場信息分發(fā)系統(tǒng)是一種使發(fā)布者和訂閱者以匿名方式進(jìn)行戰(zhàn)場信息共享的分布式系統(tǒng)。它由接入戰(zhàn)術(shù)網(wǎng)絡(luò)的信息分發(fā)代理服務(wù)器及客戶端組成。每個(gè)服務(wù)器是一個(gè)代理信息分發(fā)的節(jié)點(diǎn)，每個(gè)代理服務(wù)器節(jié)點(diǎn)為一定數(shù)量的本地客戶端提供服務(wù)，所有分發(fā)代理節(jié)點(diǎn)形成一個(gè)分布式的拓?fù)浣Y(jié)構(gòu)，如圖1 所示。戰(zhàn)場信息分發(fā)系統(tǒng)是發(fā)布/訂閱技術(shù)在軍事上的一個(gè)典型應(yīng)用，同樣具有異步、松耦合、透明傳輸?shù)奶攸c(diǎn)［6］。基于發(fā)布/訂閱的戰(zhàn)場信息分發(fā)模式適用需求廣泛，但需求用戶又不明確的戰(zhàn)場信息精準(zhǔn)分發(fā)共享，如戰(zhàn)場通用情報(bào)、氣象情報(bào)、工程情報(bào)等戰(zhàn)場情報(bào)信息以及部分戰(zhàn)場態(tài)勢信息。

圖1 戰(zhàn)場信息分發(fā)系統(tǒng)拓?fù)涫疽鈭D

1.2 戰(zhàn)場信息分發(fā)的流程

戰(zhàn)場信息分發(fā)的流程如圖1 所示，首先作戰(zhàn)用戶根據(jù)自身的信息需求通過訂閱客戶端向所在的信息分發(fā)代理服務(wù)器進(jìn)行訂閱，即圖1 中的流程①。為保證發(fā)布的信息能夠準(zhǔn)確、及時(shí)地分發(fā)給相應(yīng)的訂閱用戶，各分發(fā)代理服務(wù)器會實(shí)時(shí)地同步用戶的訂閱信息，即流程②。流程③是用戶通過發(fā)布客戶端進(jìn)行戰(zhàn)場信息（事件）發(fā)布的過程。流程④是分發(fā)代理服務(wù)器將用戶訂閱與事件進(jìn)行匹配的過程。流程⑤是事件與部分用戶訂閱匹配成功后，向其進(jìn)行分發(fā)的過程。

由于戰(zhàn)場網(wǎng)絡(luò)多為由無線連接的動態(tài)網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)會隨著各網(wǎng)絡(luò)節(jié)點(diǎn)位置的變化而產(chǎn)生變化，因此，無法使用文獻(xiàn)［4］中利用訂閱約束間的覆蓋關(guān)系來減少訂閱轉(zhuǎn)發(fā)數(shù)量的訂閱路由方法。戰(zhàn)場信息分發(fā)系統(tǒng)可采用簡單路由方法［7］，通過在分發(fā)代理網(wǎng)絡(luò)中廣播新增、變更和注銷的訂閱信息，使得所有代理節(jié)點(diǎn)都同步維護(hù)著所有用戶的訂閱信息，因此，發(fā)布的事件僅需在其本地的分發(fā)代理服務(wù)器與用戶訂閱進(jìn)行匹配，然后再分發(fā)給匹配成功的訂閱用戶。簡單路由方法對網(wǎng)絡(luò)帶寬資源的占用相對較少，但訂閱信息的維護(hù)成本相對較高，因此，訂閱信息的組織模式及維護(hù)策略將更加重要，本文將設(shè)計(jì)一種高效的訂閱信息組織模式來解決該問題。

1.3 基于內(nèi)容的戰(zhàn)場信息分發(fā)系統(tǒng)模型

要實(shí)現(xiàn)基于內(nèi)容的發(fā)布/訂閱系統(tǒng)，首先要明確系統(tǒng)的事件模型和訂閱模型。不同種類的戰(zhàn)場信息，其內(nèi)容差異較大，若建立統(tǒng)一的戰(zhàn)場信息描述模型，事件模型將過于復(fù)雜，且存在過多冗余信息。這樣的事件模型并不利于提高事件與訂閱的匹配效率，因此，可以采用目前的數(shù)字化部隊(duì)標(biāo)準(zhǔn)中定義的格式化數(shù)據(jù)報(bào)文作為系統(tǒng)的事件模型。用戶可訂閱的內(nèi)容屬性為某一戰(zhàn)場信息所有內(nèi)容屬性的一個(gè)子集，可采用XML 語言進(jìn)行組織?；趦?nèi)容的戰(zhàn)場信息分發(fā)系統(tǒng)模型如圖2 所示。

2 高效模糊匹配算法設(shè)計(jì)

目前基于內(nèi)容的發(fā)布/訂閱系統(tǒng)可以根據(jù)事件模型的數(shù)據(jù)組織方式的不同分為兩類，基于Map 的和基于XML 的。在基于Map 的發(fā)布/訂閱系統(tǒng)中，事件的內(nèi)容為多個(gè)“屬性=值”的集合，由多個(gè)“屬性=值”組成的集合為一個(gè)Map，較有影響的原型系統(tǒng)包括Gryphon、SIENA、JEDI 和Rebeca 等［7］。本文中的戰(zhàn)場信息分發(fā)系統(tǒng)本質(zhì)上是一個(gè)基于Map的發(fā)布/訂閱系統(tǒng)。在圖2 所示的信息分發(fā)代理服務(wù)器中，格式化報(bào)文解碼后被處理為多個(gè)“屬性-值”對的集合，例如（高度3 000 m）。包含用戶訂閱信息的XML 文檔被解析為多個(gè)訂閱約束的集合Sub={C1，C2…Cn}，訂閱約束Ci用一個(gè)三元組表示為（屬性，謂詞，值），例如（高度，≥，500 m）［8］。

圖2 基于內(nèi)容的戰(zhàn)場信息分發(fā)系統(tǒng)模型

2.1 模糊匹配算法的概念與流程

目前，發(fā)布/訂閱系統(tǒng)所采用的匹配算法均為嚴(yán)格的精確匹配，即一個(gè)事件要么滿足一個(gè)訂閱，要么不滿足該訂閱。而戰(zhàn)場上，作戰(zhàn)用戶對客觀信息需求的認(rèn)識有很大的主觀性，并且信息需求的表達(dá)方式也存在一定的限制，因此，用戶所表達(dá)出的信息需求是模糊的、不精確的。針對該特點(diǎn)，本文設(shè)計(jì)了一種使匹配更加合理的模糊匹配算法。

模糊匹配算法的基本思想是將用戶對某信息內(nèi)容屬性的主觀需求看作一個(gè)模糊集，而每種戰(zhàn)場信息中包含若干可訂閱的內(nèi)容屬性，因此，用戶對某戰(zhàn)場信息的需求是多個(gè)模糊集的集合。各模糊集的分布形式根據(jù)內(nèi)容屬性的特點(diǎn)并結(jié)合專家經(jīng)驗(yàn)來確定，隸屬函數(shù)的參數(shù)通過用戶的實(shí)際訂閱來確定。事件與訂閱的匹配是事件中的多個(gè)內(nèi)容屬性與訂閱中多個(gè)對應(yīng)的訂閱約束的匹配。當(dāng)有戰(zhàn)場信息發(fā)布時(shí)，通過計(jì)算該事件與對應(yīng)的多個(gè)模糊集的隸屬度來確定事件是否與用戶的訂閱匹配成功。在精確匹配算法中，若存在一對事件內(nèi)容屬性與訂閱約束匹配失敗，則整個(gè)事件與訂閱的匹配將被判定為匹配失敗，而在模糊匹配算法中，部分事件內(nèi)容屬性與訂閱約束的匹配結(jié)果不會決定整個(gè)事件和訂閱的匹配結(jié)果，而需要綜合所有訂閱約束與事件內(nèi)容屬性的匹配結(jié)果來進(jìn)行綜合判定。

在某戰(zhàn)場信息中，不同的內(nèi)容屬性對某一用戶來說其重要程度是不同的，如空中目標(biāo)信息，目標(biāo)的位置信息要比目標(biāo)的航向重要，目標(biāo)的航向要比目標(biāo)的速度、高度重要，因此，在模糊匹配過程中，不同內(nèi)容屬性的隸屬度對整個(gè)事件與訂閱匹配度的影響程度也是不一樣的。內(nèi)容屬性對用戶的重要性越大，其在事件與訂閱的匹配中所起的作用也應(yīng)越大，因此，可以先通過層次分析法（AHP）等方法確定某戰(zhàn)場信息中各內(nèi)容屬性的相對權(quán)重，然后再計(jì)算各內(nèi)容屬性隸屬度的加權(quán)平均數(shù)，作為整個(gè)事件與用戶訂閱的匹配度。

綜上所述，可將發(fā)布的某戰(zhàn)場信息與某用戶訂閱信息的模糊匹配流程總結(jié)如下：

1）確定用戶訂閱中各訂閱約束模糊集的隸屬函數(shù)，設(shè)訂閱約束Ci的隸屬函數(shù)為μi（x）；

2）確定該戰(zhàn)場信息中各內(nèi)容屬性的權(quán)重，設(shè)事件中屬性Attri的相對權(quán)重為ωi；

3）計(jì)算事件中各內(nèi)容屬性與對應(yīng)訂閱約束模糊集的隸屬度，若事件中內(nèi)容屬性Attri的取值為xi，則Attri在對應(yīng)訂閱約束模糊集中的隸屬度為μi（xi）；

4）計(jì)算發(fā)布事件與該用戶訂閱的匹配度M；

5）判定發(fā)布事件與用戶訂閱是否匹配成功，若該匹配度M 大于等于用戶設(shè)定的匹配度閾值M，則可判定事件與該用戶的訂閱匹配成功，否則就判定為匹配失敗。

2.2 高效模糊匹配算法

通過分析發(fā)現(xiàn)，上述模糊匹配方法需要逐用戶、逐屬性地計(jì)算事件與所有用戶訂閱的匹配度，然后才能最終判定出事件與哪些用戶的訂閱匹配成功。當(dāng)戰(zhàn)場信息分發(fā)系統(tǒng)的規(guī)模較大，用戶的訂閱數(shù)量較多時(shí)，模糊匹配算法的時(shí)間效率將大大降低，戰(zhàn)場信息分發(fā)的及時(shí)性將難以保證，因此，需要一種在不降低模糊匹配算法合理性的同時(shí)，又能有效提高其匹配效率的方法。

提高匹配效率的一種思路是縮小與事件進(jìn)行模糊匹配的訂閱范圍，即通過已有的精確匹配算法快速地篩選出一部分有可能與發(fā)布事件匹配成功的用戶訂閱，只通過模糊匹配算法計(jì)算這一小部分訂閱信息與發(fā)布事件的匹配度。如圖3 所示，S0為所有用戶的訂閱，S2假設(shè)為能夠與發(fā)布事件匹配成功的用戶訂閱，則集合S1即經(jīng)精確匹配快速篩選出的用戶訂閱，只將S1中的訂閱與事件進(jìn)行模糊匹配，這樣既保證了匹配的合理性，又提高了匹配的效率。

圖3 用戶訂閱的集合關(guān)系

為實(shí)現(xiàn)上述快速、精確的匹配，需要將用戶的原始訂閱進(jìn)行模糊預(yù)處理。在確定了用戶訂閱約束模糊集的隸屬函數(shù)后，取某一較小的隸屬度數(shù)值作為隸屬度模糊閾值，將該閾值對應(yīng)的訂閱約束值作為該用戶新的訂閱約束值進(jìn)行精確匹配。如圖4 所示，設(shè)某戰(zhàn)場信息中包含內(nèi)容屬性A，由某用戶的訂閱確定了圖中的隸屬度函數(shù)曲線，某用戶對屬性A的實(shí)際訂閱為區(qū)間［a，b］。取隸屬度0.3 作為模糊閾值，則屬性A 的訂閱范圍經(jīng)模糊預(yù)處理后變?yōu)閰^(qū)間［a0，b0］。對所有用戶訂閱信息的所有可訂閱屬性進(jìn)行上述模糊預(yù)處理后，再與發(fā)布事件進(jìn)行快速的精確匹配，所得匹配結(jié)果即為圖4 中的集合S1。

圖4 用戶訂閱的模糊預(yù)處理過程

通過上述分析可知，所有用戶訂閱均需要和發(fā)布事件進(jìn)行一次精確匹配，才能篩選出一部分用戶訂閱與發(fā)布事件進(jìn)行模糊匹配，因此，事件與訂閱進(jìn)行精確匹配的效率同樣制約著整個(gè)模糊匹配算法的效率。提高精確匹配算法效率的基本思路是優(yōu)化用戶訂閱信息的組織結(jié)構(gòu)，減少匹配過程中對相同訂閱約束的判斷次數(shù)，以此提高匹配的時(shí)間效率［3］。

2.3 訂閱約束間的邏輯覆蓋關(guān)系

不同的用戶可能會通過相同的內(nèi)容屬性來訂閱同一種戰(zhàn)場信息，因此，訂閱集合中會存在訂閱約束之間的邏輯覆蓋關(guān)系。例如，用戶a 和用戶b 均通過高度屬性訂閱了同一戰(zhàn)場信息，其中Cai=（高度，≥，5 000 m），Cbj=（高度，≥，10 000 m），則訂閱約束Cai和Cbj之間就存在邏輯上的覆蓋關(guān)系，即發(fā)布事件中的高度屬性滿足約束Cbj時(shí)，就必然滿足約束Cai。由于Cbj是Cai成立的充分條件，因此，可以通過設(shè)計(jì)特定的數(shù)據(jù)結(jié)構(gòu)，充分利用約束間的邏輯覆蓋關(guān)系來減少不必要的比較操作。例如，可合并相同的訂閱約束并用數(shù)組將約束值按大小順序排列，然后使用二分法進(jìn)行查找，當(dāng)找到第一個(gè)與事件屬性值匹配成功的訂閱約束值后，就可以確定所有訂閱約束值的匹配結(jié)果了。

為利用上述訂閱約束間的邏輯覆蓋關(guān)系，并提高訂閱信息的查找效率，建立如圖5 所示的多級索引結(jié)構(gòu)，其中關(guān)系運(yùn)算符索引指向的是用戶所訂閱的信息內(nèi)容屬性約束值［9］。為組織大量的訂閱約束值，可考慮的數(shù)據(jù)結(jié)構(gòu)包括順序存儲結(jié)構(gòu)（如數(shù)組、隊(duì)列），鏈?zhǔn)酱鎯Y(jié)構(gòu)（如鏈表、二叉樹）。

圖5 用戶訂閱信息的數(shù)據(jù)結(jié)構(gòu)

2.4 匹配算法中訂閱信息組織模式的設(shè)計(jì)

在采用簡單事件路由方法的戰(zhàn)場信息分發(fā)系統(tǒng)中，為提高內(nèi)容匹配的時(shí)間效率并降低訂閱信息的維護(hù)成本，需要對用戶訂閱信息的組織模式進(jìn)行設(shè)計(jì)［10-14］。以順序存儲結(jié)構(gòu)存儲用戶訂閱信息為例，所有謂詞約束均為小于等于約束，則利用約束間的邏輯覆蓋關(guān)系可以將用戶訂閱的約束值組織為如圖6 所示的3 種形式。圖6（a）為簡單的邏輯覆蓋模式，其中Vi 為按升序排列的約束值，下面對應(yīng)的Ui 為訂閱中約束值是Vi 的用戶。當(dāng)進(jìn)行匹配時(shí)，對Vi 進(jìn)行二分查找，查找到大于等于屬性值Ei 的約束值v 后，對v 后面的用戶進(jìn)行遍歷即可得到匹配結(jié)果。圖6 模式（b）是對圖6（a）的改進(jìn)，將約束值大于等于Vi 的所有用戶放到Vi 的用戶隊(duì)列中。當(dāng)進(jìn)行匹配時(shí)，只需進(jìn)行二分查找即可得到匹配結(jié)果，省去了遍歷后面用戶的操作，可以有效地提高匹配的時(shí)間效率。但這種完全邏輯覆蓋模式的空間復(fù)雜度極差，空間復(fù)雜度為O（n2），并且訂閱維護(hù)的效率也很低，不具備實(shí)用性。

對圖6 模式（b）進(jìn)行改進(jìn)，得到圖6（c）所示的分段完全邏輯覆蓋模式。在圖6 模式（c）中約束值在整體上是無序的，但在分段區(qū)間內(nèi)是有序的，每個(gè)分段區(qū)間內(nèi)部采用完全邏輯覆蓋模式。當(dāng)進(jìn)行匹配時(shí)，對每個(gè)區(qū)間分別進(jìn)行二分查找操作，將各個(gè)分段區(qū)間內(nèi)的匹配結(jié)果合在一起即為最終匹配的結(jié)果。這種模式下，設(shè)分段空間的大小為N，則匹配的時(shí)間復(fù)雜度為O（logN*n/N+n）=O（n），空間復(fù)雜度為O（1/2（N*（N+1））*（n/N））=O（n），訂閱約束值插入的時(shí)間復(fù)雜度為O（logN+N）=常數(shù)階。采用空值代替的方法，訂閱約束值刪除操作的時(shí)間復(fù)雜度也是常數(shù)階。3 種模式的對比如表1 所示。

表1 3 種模式性能對比

圖6 小于等于約束中約束值的組織模式

3 實(shí)驗(yàn)驗(yàn)證與分析

實(shí)驗(yàn)程序所運(yùn)行的計(jì)算機(jī)采用Windows XP Professional sp3 操作系統(tǒng)，CPU 為Intel Core Quad Q9400 2.66 GHz，內(nèi)存為2 G DDR3。實(shí)驗(yàn)程序使用C++語言在VC++6.0 上編寫。以擁有3 個(gè)可訂閱屬性的某信息作為事件來模擬其發(fā)布和訂閱的過程，假設(shè)訂閱約束均為一元謂詞約束，并采用vector 容器來組織用戶的約束值。訂閱約束值由Box-Muller方法產(chǎn)生的符合正態(tài)分布的隨機(jī)數(shù)進(jìn)行模擬。3 個(gè)屬性的訂閱約束值的分布分別為N（500，100），N（1 000，300），N（1 500，500），并以3 個(gè)正態(tài)分布的均值作為發(fā)布的事件，即Event={500，1 000，1 500}。

實(shí)驗(yàn)結(jié)果如圖7～圖9 所示，其中3 種模式的匹配效率和訂閱維護(hù)效率的實(shí)驗(yàn)結(jié)果如圖7 和圖8所示，其中模式c 的分段區(qū)間N 為1 000。實(shí)驗(yàn)所得結(jié)果和表1 中時(shí)間復(fù)雜度的理論分析結(jié)果一致，對比可知，模式c 是一種最優(yōu)方案。在采用簡單事件路由方法的戰(zhàn)場信息分發(fā)系統(tǒng)中，模式c 在保證較高匹配效率的同時(shí)，還能夠有效控制和降低分發(fā)代理節(jié)點(diǎn)維護(hù)訂閱信息的成本。

圖7 3 種模式匹配效率對比

圖8 3 種模式訂閱維護(hù)效率對比

圖9為采用模式c 的匹配算法中不同的訂閱數(shù)據(jù)規(guī)模情況下，分段區(qū)間大小N 與匹配時(shí)間之間的關(guān)系。從曲線變化的規(guī)律可以看出是一種負(fù)指數(shù)函數(shù)的規(guī)律，且不同的用戶規(guī)模所對應(yīng)的最優(yōu)分段區(qū)間大小是不同的，為保證較高的匹配效率，應(yīng)隨著訂閱數(shù)據(jù)規(guī)模的增加適當(dāng)增加分段區(qū)間N 的大小。

圖9 匹配時(shí)間與分段區(qū)間大小的關(guān)系

模式c 中分段區(qū)間N 的取值應(yīng)根據(jù)系統(tǒng)的規(guī)模（用戶數(shù)量、可訂閱信息數(shù)量和每種信息平均可訂閱屬性的數(shù)量）和信息分發(fā)服務(wù)器內(nèi)存的大小來選擇合適的值。設(shè)訂閱用戶的數(shù)量為n，可訂閱的信息的數(shù)量為M，信息中平均可訂閱的屬性數(shù)量為A，分段區(qū)間大小為N，用戶標(biāo)識Ui 占用的內(nèi)存大小為T，則該訂閱結(jié)構(gòu)占用的內(nèi)存大小G 滿足下式

4 結(jié)論

本文首先針對戰(zhàn)場信息分發(fā)的需求，設(shè)計(jì)了基于內(nèi)容的戰(zhàn)場信息分發(fā)系統(tǒng)模型，然后考慮到戰(zhàn)場上作戰(zhàn)用戶對信息需求認(rèn)識與表達(dá)的主觀性和模糊性，利用模糊集理論，并結(jié)合精確匹配算法，設(shè)計(jì)了高效模糊匹配算法的思想與流程，最后為提高匹配算法的時(shí)間效率，并降低訂閱信息的維護(hù)成本，設(shè)計(jì)了組織訂閱信息的分段完全邏輯覆蓋模式，并通過實(shí)驗(yàn)驗(yàn)證了該模式設(shè)計(jì)的合理性。該高效模糊匹配算法，能夠同時(shí)保證戰(zhàn)場信息分發(fā)系統(tǒng)內(nèi)容匹配的合理性與高效性，算法中戰(zhàn)場信息內(nèi)容屬性的隸屬函數(shù)的確定等內(nèi)容有待進(jìn)一步研究。