王 敏,李萬(wàn)春,扶彩霞,郭昱寧
(電子科技大學(xué)信息與通信工程學(xué)院,四川 成都 611731)
戰(zhàn)術(shù)數(shù)據(jù)鏈?zhǔn)菬o(wú)線(xiàn)網(wǎng)絡(luò)通信在軍事方面的典型應(yīng)用,典型數(shù)據(jù)鏈如Link16。戰(zhàn)場(chǎng)環(huán)境下數(shù)據(jù)鏈網(wǎng)絡(luò)根據(jù)不同作戰(zhàn)任務(wù)和功能,形成一個(gè)層次化網(wǎng)絡(luò),包括指揮平臺(tái)、作戰(zhàn)平臺(tái)、傳感探測(cè)平臺(tái)。數(shù)據(jù)鏈層次分析可以獲得區(qū)域內(nèi)各個(gè)電磁激勵(lì)源之間的多層次的網(wǎng)絡(luò)關(guān)系,從而掌握區(qū)域內(nèi)電磁綜合狀態(tài)、作戰(zhàn)進(jìn)程和效果評(píng)估,最終把握空間網(wǎng)絡(luò)中的目標(biāo)承載、通聯(lián)關(guān)系與拓?fù)浣Y(jié)構(gòu)。數(shù)據(jù)鏈網(wǎng)絡(luò)中的拓?fù)潢P(guān)系研究已經(jīng)成為網(wǎng)絡(luò)對(duì)抗領(lǐng)域的熱門(mén)研究方向之一。在實(shí)際場(chǎng)景中,由于各個(gè)輻射源的通信行為、不同區(qū)域不同輻射源協(xié)同作戰(zhàn)情況動(dòng)態(tài)變化,因此從一個(gè)無(wú)中心節(jié)點(diǎn)的數(shù)據(jù)鏈網(wǎng)絡(luò)中挖掘不同節(jié)點(diǎn)的層次關(guān)系就顯得十分重要[1-4]。
數(shù)據(jù)鏈網(wǎng)絡(luò)層次發(fā)現(xiàn)屬于數(shù)據(jù)挖掘領(lǐng)域。數(shù)據(jù)挖掘是從大量的、不完全、有噪聲、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中,提取隱含在其中、人們事先不知道的但又是有用的信息和知識(shí)的過(guò)程[5]。數(shù)據(jù)挖掘是一項(xiàng)交叉學(xué)科,目前主要作為一種新的商業(yè)信息處理技術(shù),其主要特點(diǎn)是對(duì)商業(yè)數(shù)據(jù)庫(kù)中的大量業(yè)務(wù)數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換、分析和其他模型化處理,從中提取輔助決策的關(guān)鍵性數(shù)據(jù)[6-8]。數(shù)據(jù)挖掘可以描述為:按照既定的業(yè)務(wù)目標(biāo),對(duì)大量數(shù)據(jù)按照一定的算法進(jìn)行探索和分析,揭示隱藏的、未知的或驗(yàn)證已知的規(guī)律性。在目前關(guān)聯(lián)規(guī)則算法中最成熟的是Apriori算法[9-10]。
早期學(xué)者們對(duì)數(shù)據(jù)鏈拓?fù)潢P(guān)系的研究主要集中在移動(dòng)自組網(wǎng)(mobile ad hoc network,簡(jiǎn)稱(chēng)MANET)上,它是一種不依賴(lài)任何固定設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò),且與戰(zhàn)術(shù)數(shù)據(jù)鏈網(wǎng)絡(luò)相比有較大區(qū)別,網(wǎng)絡(luò)拓?fù)洳捎霉?jié)點(diǎn)隨機(jī)分布的方式,沒(méi)有體現(xiàn)數(shù)據(jù)鏈網(wǎng)絡(luò)層次化的特點(diǎn)[11]。因此本文提出一種基于Apriori算法的網(wǎng)絡(luò)層次拓?fù)浒l(fā)現(xiàn)方法,該方法結(jié)合數(shù)據(jù)挖掘與聚類(lèi)方法,揭示隱含的數(shù)據(jù)鏈網(wǎng)絡(luò)層次關(guān)系,能夠體現(xiàn)戰(zhàn)場(chǎng)環(huán)境下節(jié)點(diǎn)層次化特征,實(shí)現(xiàn)在網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布情況下挖掘出不同節(jié)點(diǎn)之間的層次關(guān)系和關(guān)聯(lián)程度。
Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。比如著名的購(gòu)物籃分析案例:70%購(gòu)買(mǎi)了牛奶的顧客將傾向于同時(shí)購(gòu)買(mǎi)面包;在超市中與尿布一起被購(gòu)買(mǎi)最多的商品竟然是啤酒。算法使用逐層搜索的迭代方法,“k-1項(xiàng)集”用于探索“k項(xiàng)集”,尋找最大項(xiàng)目集需要對(duì)數(shù)據(jù)集進(jìn)行多次迭代處理。該算法的核心思想是通過(guò)候選集生成和向下封閉檢測(cè)來(lái)挖掘頻繁項(xiàng)集。算法的相關(guān)概念如下。關(guān)聯(lián)規(guī)則:反應(yīng)一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果2個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系,那么,其中一個(gè)事物就能夠通過(guò)其他事物預(yù)測(cè)到。事務(wù):訪(fǎng)問(wèn)并可能更新數(shù)據(jù)庫(kù)中各種數(shù)據(jù)項(xiàng)的一個(gè)程序執(zhí)行單元。項(xiàng)集:項(xiàng)目的集合稱(chēng)為項(xiàng)目集合,簡(jiǎn)稱(chēng)為項(xiàng)集。其元素個(gè)數(shù)稱(chēng)為項(xiàng)集的長(zhǎng)度,長(zhǎng)度為k的項(xiàng)集稱(chēng)為k項(xiàng)集。支持度:項(xiàng)集中包含項(xiàng)目A∪B的百分比,支持度表示在規(guī)則中出現(xiàn)的頻度。support(A→B)=P(A∪B)
(1)
頻繁項(xiàng)集:支持度大于等于某個(gè)閾值的項(xiàng)集。置信度:數(shù)據(jù)集中包含A事務(wù)的同時(shí)包含B事務(wù)的百分比。置信度表示規(guī)則的強(qiáng)度。
confidence(A→B)=P(A∪B)/P(A)confidence(B→A)=P(A∪B)/P(B)
(2)
發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要求項(xiàng)集必須滿(mǎn)足的最小支持閾值,稱(chēng)為項(xiàng)集的最小支持度,記為supmin。支持度大于或等于supmin的項(xiàng)集稱(chēng)為頻繁項(xiàng)集,簡(jiǎn)稱(chēng)頻繁集,反之稱(chēng)為非頻繁集。通常k項(xiàng)集如果滿(mǎn)足supmin,稱(chēng)為k頻繁集,記為L(zhǎng)k。強(qiáng)關(guān)聯(lián)規(guī)則:如果規(guī)則R滿(mǎn)足:
support(R)≥supminconfidence(R)≥confmin
(3)
則稱(chēng)關(guān)聯(lián)規(guī)則R為強(qiáng)關(guān)聯(lián)規(guī)則,否則稱(chēng)關(guān)聯(lián)規(guī)則R為弱關(guān)聯(lián)規(guī)則。在挖掘關(guān)聯(lián)規(guī)則時(shí),產(chǎn)生的關(guān)聯(lián)規(guī)則要經(jīng)過(guò)supmin和confmin的衡量。另外,Apriori算法的2個(gè)重要性質(zhì)如下:性質(zhì)1:頻繁項(xiàng)集的子集必為頻繁項(xiàng)集。性質(zhì)2:非頻繁項(xiàng)集的超集一定是非頻繁的。
根據(jù)Link16通信協(xié)議,所有節(jié)點(diǎn)在所屬的時(shí)隙內(nèi)發(fā)送消息,任何節(jié)點(diǎn)都可以在不發(fā)送消息的時(shí)隙內(nèi)接收消息。那么就導(dǎo)致大量的未知信息,接收消息節(jié)點(diǎn)未知使得發(fā)現(xiàn)數(shù)據(jù)鏈通連關(guān)系的難度變大。再者,Link16屬于無(wú)中心網(wǎng)絡(luò),相比于Link11有中心網(wǎng)絡(luò),Link16節(jié)點(diǎn)的發(fā)送順序沒(méi)有規(guī)律性,帶有很大的隨機(jī)性。針對(duì)戰(zhàn)術(shù)數(shù)據(jù)鏈偵察消息量大、節(jié)點(diǎn)隨機(jī)分布的特點(diǎn),在偵察信息先驗(yàn)知識(shí)基礎(chǔ)上,本文利用數(shù)據(jù)挖掘算法的思想,把對(duì)應(yīng)的層次拓?fù)洚?dāng)做頻繁項(xiàng)集來(lái)進(jìn)行關(guān)聯(lián)規(guī)則挖掘。如果節(jié)點(diǎn)在Link16的協(xié)議下組網(wǎng),高級(jí)指揮平臺(tái)發(fā)送命令控制類(lèi)消息給次級(jí)指揮平臺(tái),次級(jí)指揮平臺(tái)會(huì)在一定概率Psend下作出反應(yīng),可能會(huì)發(fā)送消息給次級(jí)平臺(tái),也可能會(huì)發(fā)送應(yīng)答消息。那么消息可能會(huì)沿著拓?fù)鋱D中的邊向下傳遞,在時(shí)間上形成屬于該集群的消息序列集合。由于消息的應(yīng)答與傳遞存在一定的概率Psend,導(dǎo)致了在層次關(guān)系上最接近的節(jié)點(diǎn)的關(guān)聯(lián)程度support最高,跨級(jí)之間的關(guān)聯(lián)度support隨之減小,因此support大的節(jié)點(diǎn)具有層次關(guān)系。結(jié)合流量統(tǒng)計(jì)數(shù)據(jù)等先驗(yàn)知識(shí),先選取流量最大的節(jié)點(diǎn)對(duì)消息序列做分割;將每個(gè)時(shí)間段內(nèi)不同平臺(tái)的消息作為Apriori算法中每次交易項(xiàng)目集中的項(xiàng)目;分割所得的消息集合作為項(xiàng)目集,2種關(guān)系對(duì)比如表1所示。
表1 Apriori算法與Link16數(shù)據(jù)鏈術(shù)語(yǔ)對(duì)比
定義節(jié)點(diǎn)之間的關(guān)聯(lián)規(guī)則:設(shè)最小支持度為support(R),最小置信度為confidence(R),當(dāng)節(jié)點(diǎn)之間的消息序列集合的最小支持度和最小置信度滿(mǎn)足:
support(R)≥supminconfidence(R)≥confmin
(4)
認(rèn)為節(jié)點(diǎn)之間一定存在從屬關(guān)系?;谝陨厦枋?,數(shù)據(jù)鏈網(wǎng)絡(luò)層次關(guān)系挖掘算法描述如下:算法名稱(chēng):基于Apriori算法的數(shù)據(jù)鏈層次關(guān)系挖掘算法。輸入:最小支持度,最小置信度和仿真消息序列。輸出:數(shù)據(jù)鏈網(wǎng)絡(luò)的層次拓?fù)潢P(guān)系。Step 1: 在多層次的網(wǎng)絡(luò)中,為每個(gè)節(jié)點(diǎn)分配時(shí)隙,并設(shè)定最小支持度和最小置信度;Step 2: 統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)發(fā)送消息的頻率,將頻率大于等于最小支持度的節(jié)點(diǎn)構(gòu)成頻繁k-2項(xiàng)集;Step 3: 對(duì)獲得的頻繁k-1項(xiàng)集中節(jié)點(diǎn)集合進(jìn)行掃描計(jì)數(shù),統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)集合發(fā)送消息的頻率,將頻率不小于最小支持度的節(jié)點(diǎn)構(gòu)成頻繁k-2項(xiàng)集;Step4: 重復(fù)上述過(guò)程,直到獲得頻繁k維項(xiàng)目集;Step 5:根據(jù)獲得的k維頻繁項(xiàng)目集,計(jì)算置信度,根據(jù)置信度得出節(jié)點(diǎn)之間的從屬關(guān)系,獲得不同節(jié)點(diǎn)之間的層次關(guān)系。Step 2的具體步驟為:從多個(gè)節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)的時(shí)隙作為分隔條件,從而統(tǒng)計(jì)出各個(gè)節(jié)點(diǎn)的發(fā)送消息的頻率,再將頻率不小于最小支持度的節(jié)點(diǎn)構(gòu)成頻繁k-1項(xiàng)集。
圖1 節(jié)點(diǎn)層次關(guān)系拓?fù)鋱D
圖2 8個(gè)平臺(tái)的消息時(shí)序圖
在實(shí)際環(huán)境中,一般一個(gè)作戰(zhàn)集群都會(huì)有一個(gè)最高的指揮節(jié)點(diǎn),向下繼續(xù)拓展會(huì)有次級(jí)指揮節(jié)點(diǎn)直到普通的作戰(zhàn)單元。如圖1所示為8個(gè)節(jié)點(diǎn)的層次拓?fù)鋱D。為了評(píng)估方法性能,設(shè)定如下簡(jiǎn)化場(chǎng)景進(jìn)行仿真。在某確定的Link16數(shù)據(jù)鏈網(wǎng)絡(luò)中,I={A,B,C,D,E,F,G,H}為該網(wǎng)絡(luò)的節(jié)點(diǎn),其中A是一級(jí)指揮平臺(tái),B是次級(jí)指揮平臺(tái),C,D是無(wú)人機(jī)偵察平臺(tái),E,F,G,H是作戰(zhàn)平臺(tái)。下面將通過(guò)仿真驗(yàn)證本文算法得到的層次拓?fù)渑c設(shè)定網(wǎng)絡(luò)完全一致。根據(jù)Link16數(shù)據(jù)鏈時(shí)隙分配規(guī)則,給圖1中的8個(gè)節(jié)點(diǎn)分配時(shí)隙。并假設(shè)設(shè)置Psend=0.8,supmin=0.6,confmin=0.6,8個(gè)節(jié)點(diǎn)的消息序列服從泊松分布,根據(jù)戰(zhàn)術(shù)數(shù)據(jù)鏈分配規(guī)則,給8個(gè)節(jié)點(diǎn)分配時(shí)隙,8個(gè)節(jié)點(diǎn)的消息時(shí)序如圖2所示。用A節(jié)點(diǎn)的消息作為分隔條件,就可以得到如表2所示的數(shù)據(jù)表。
表2 數(shù)據(jù)表
圖3 各個(gè)平臺(tái)的支持度
圖4 候選頻繁k-2項(xiàng)集支持度
圖5 候選頻繁k-2項(xiàng)集置信度
所以可以認(rèn)為該數(shù)據(jù)鏈的層次拓?fù)渲杏蠥→B→C和A→B→D的關(guān)系。因?yàn)閷哟伪容^低的節(jié)點(diǎn)在以A時(shí)隙為分割點(diǎn)的情況下不滿(mǎn)足:
support(R)≥supmin
圖6 平臺(tái)B-H的消息時(shí)序圖
圖7 頻繁k-1項(xiàng)集的支持度
圖8 頻繁k-2項(xiàng)集的支持度
所以此時(shí)要想獲得{{E},{F},{G},{H}}的層次關(guān)系,就需要使分割點(diǎn)的層級(jí)級(jí)別降低并去除比新分割節(jié)點(diǎn)層次高的節(jié)點(diǎn)。例如,再選擇B節(jié)點(diǎn)的時(shí)隙作為時(shí)隙分割點(diǎn),那么就需要先去除A節(jié)點(diǎn)的時(shí)隙信息,避免增加挑選頻繁項(xiàng)集的復(fù)雜度。以B的時(shí)隙作為時(shí)隙分割點(diǎn),得到剩余節(jié)點(diǎn)的時(shí)隙序列,如圖6所示。得到頻繁k-1項(xiàng)集的支持度,如圖7所示。由于所有平臺(tái)的支持度都滿(mǎn)足最小支持度的要求,所以繼續(xù)求解頻繁k-2項(xiàng)集的支持度,由于從第一次求解過(guò)程中已經(jīng)求得節(jié)點(diǎn)B和節(jié)點(diǎn)CD的關(guān)系,所以在本次迭代過(guò)程中可以不求B節(jié)點(diǎn)和節(jié)點(diǎn)CD的關(guān)系。得到的曲線(xiàn)圖如圖8所示。從圖8中可以看出{CE},{CF},{DG},{DH}的支持度滿(mǎn)足條件,那么將{{CE},{CF},{DG},{DH}}作為候選頻繁k-2項(xiàng)集。得到的置信度如表3所示。
表3 置信度
從表3中可以看出置信度滿(mǎn)足條件,即存在層次關(guān)系{C→E},{C→F},{D→G},{D→H}??偨Y(jié)以上過(guò)程,通過(guò)該算法迭代得到層次拓?fù)潢P(guān)系為{A→B→C→E}、{A→B→C→F}、{A→B→D→G}、{A→B→D→H},與設(shè)定的網(wǎng)絡(luò)完全一致。從上述過(guò)程也可以看出,在層次拓?fù)鋱D中層次越高,k-1、k-2項(xiàng)集支持度越高;層次拓?fù)渲?個(gè)節(jié)點(diǎn)越相近,置信度越高;置信度反映了關(guān)聯(lián)規(guī)則的強(qiáng)弱,置信度越高從屬關(guān)系越明顯。當(dāng)2個(gè)節(jié)點(diǎn)跨層次時(shí)(如AC),置信度反而下降。當(dāng)節(jié)點(diǎn)在特定協(xié)議下組網(wǎng),那么消息可能會(huì)沿著拓?fù)鋱D的邊向下傳遞,在時(shí)間上形成屬于該集群的消息序列集合。由于消息的應(yīng)答和傳遞存在一定的概率P,導(dǎo)致了在層次關(guān)系上最接近的節(jié)點(diǎn)的關(guān)聯(lián)程度最高,跨級(jí)之間的關(guān)聯(lián)度隨之減小,這符合實(shí)際作戰(zhàn)情況。
本文提出一種基于Apriori算法的層次拓?fù)渫诰蚍椒?,解決了數(shù)據(jù)鏈網(wǎng)絡(luò)在無(wú)中心節(jié)點(diǎn)的情況下準(zhǔn)確找到節(jié)點(diǎn)的層次拓?fù)潢P(guān)系的途徑。通過(guò)迭代得到k項(xiàng)集,找出滿(mǎn)足支持度和置信度的候選集,同時(shí)滿(mǎn)足最小支持度和最小置信度的候選集為頻繁項(xiàng)集,找出頻繁項(xiàng)集的節(jié)點(diǎn)之間的從屬關(guān)系。仿真實(shí)驗(yàn)表明,該算法能有效挖掘數(shù)據(jù)鏈網(wǎng)絡(luò)的層次關(guān)系。該算法的下一步研究方向,是適應(yīng)大型的、實(shí)際的非合作戰(zhàn)場(chǎng)網(wǎng)絡(luò)。■