基于最大似然的網(wǎng)絡(luò)拓?fù)渫茢嗉夹g(shù)研究（一）

本節(jié)基于廣義似然比檢測通過對子樹序貫合并來推斷樹狀拓?fù)洹Ｎ墨I(xiàn)[6，9]應(yīng)用了節(jié)點(diǎn)合并的方法推斷拓?fù)洌湔业阶钕嚓P(guān)子樹之后都按照二叉樹來合并，這顯然與真實(shí)情況相去甚遠(yuǎn)。本算法的創(chuàng)新之處在于：分析了最相關(guān)子樹的各種可能的合并方式；提出了基于廣義似然比檢測的子樹合并方式判定方法。

3.1 子樹合并

3.1.1 尋找最相關(guān)子樹

首先給出子樹相關(guān)性的定義，任取兩顆子樹Ti，Tj，二者的葉子節(jié)點(diǎn)集合分別為U和V，葉子節(jié)點(diǎn)個(gè)數(shù)分別為K，L，則子樹Ti與Tj之間的相關(guān)性定義為

式中，γkl為子樹Ti中的葉子節(jié)點(diǎn)k與子樹Tj中的葉子節(jié)點(diǎn)l的相關(guān)性。

定理2：如果序貫合并過程中每次選擇的兩棵子樹{Ti,Tj}均為最相關(guān)子樹，則每次子樹合并的合并點(diǎn)（兩樹合并的接觸點(diǎn)）在合并后的樹中僅可能體現(xiàn)為原子樹的根節(jié)點(diǎn)或者原子樹根節(jié)點(diǎn)的父節(jié)點(diǎn)。其中合并點(diǎn)是為合并兩顆子樹而創(chuàng)建的新節(jié)點(diǎn)，如圖2中節(jié)點(diǎn)q。

證明：反證法，不失一般性，我們假設(shè)兩子樹的合并點(diǎn)為左子樹Ti根節(jié)點(diǎn)的孩子節(jié)點(diǎn)，如圖2所示，實(shí)線表示左子樹Ti，虛線表示右子樹Tj，兩子樹合并點(diǎn)為q，則q為左子樹根節(jié)點(diǎn)i的孩子節(jié)點(diǎn)，那么此時(shí)從源節(jié)點(diǎn)s到節(jié)點(diǎn)i的鏈路長度要小于從源節(jié)點(diǎn)s到節(jié)點(diǎn)q的鏈路長度，則可得（1）：子樹b與子樹j的相關(guān)性大于子樹a和子樹b的相關(guān)性；而又由于序貫合并過程中每次選擇的子樹對{i,j}均為最相關(guān)子樹，則可得（2）：子樹b與子樹j的相關(guān)性小于子樹a和子樹b的相關(guān)性。顯然（1）與（2）矛盾，因此如果滿足序貫合并過程中每次選擇的子樹對{i,j}均為最相關(guān)子樹，則每次子樹合并的合并點(diǎn)必為子樹的根節(jié)點(diǎn)或者子樹根節(jié)點(diǎn)的父節(jié)點(diǎn)，而不可能是兩棵子樹根節(jié)點(diǎn)的孩子節(jié)點(diǎn)。

圖2 子樹合并示意圖

給定子樹集合{Tl,l=1,…L}，任取其中兩顆子樹Ti，Tj，二者的葉子節(jié)點(diǎn)集合分別為U和V。子樹Ti所有葉子節(jié)點(diǎn)與Tj所有葉子節(jié)點(diǎn)之間的相關(guān)性集合為Γ＝｛γuv，u∈U，v∈V }，u，v分別為子樹Ti與Tj的葉子節(jié)點(diǎn)。由于對于任意u和v，在其待推斷的真實(shí)拓?fù)渲芯哂邢嗤淖钌罡腹?jié)點(diǎn)，所以由定理1得，集合Γ中所有元素都有相同的數(shù)值，定義這個(gè)數(shù)值為子樹之間的相關(guān)性γij。根據(jù)性質(zhì)1，我們可以認(rèn)為子樹Ti任意葉子節(jié)點(diǎn)u與Tj的任意葉子節(jié)點(diǎn)v之間的相關(guān)性采樣值，n=1,…,N，都服從相同的高斯分布N(γij,σ2)，因此可根據(jù)（1）式估計(jì)Ti，Tj的相關(guān)性

3.1.2 子樹合并方式

在找到最相關(guān)子樹對之后，需要判定子樹的合并方式。兩個(gè)子樹的合并可分為三種情況，1）葉子節(jié)點(diǎn)數(shù)目均為1的兩子樹合并；2）葉子節(jié)點(diǎn)個(gè)數(shù)為1的子樹與葉子節(jié)點(diǎn)數(shù)不為1的子樹的合并；3）兩個(gè)葉子節(jié)點(diǎn)數(shù)目都不為1的子樹的合并。

由定理2可得，在情況1）中子樹的合并方式僅有一種，如圖3所示；情況2）中子樹有四種可能的合并方式如圖4所示；情況3）中子樹也有四種可能的合并方式，如圖5所示。圖中葉子節(jié)點(diǎn)數(shù)不為1的子樹由有兩個(gè)葉子節(jié)點(diǎn)的樹代表，實(shí)線表示左子樹，虛線表示右子樹。

圖3 情況1的合并方式

圖4 情況2的合并方式

圖5 情況3的合并方式

設(shè)左右子樹的根節(jié)點(diǎn)分別為i和j，合并點(diǎn)為q，我們只需確定i，j，q中哪些點(diǎn)為相同的節(jié)點(diǎn)，即可推斷出子樹以哪一種方式合并。對于情況1）只有一種合并方式；對于情況2）只需判斷節(jié)點(diǎn)數(shù)不為1的子樹的根節(jié)點(diǎn)是否與合并點(diǎn)q為相同的節(jié)點(diǎn)即可；對于情況3）我們需要判斷兩個(gè)子樹的根節(jié)點(diǎn)是否與合并點(diǎn)q為相同的節(jié)點(diǎn)。例如在情況3）的a方式（圖5）中i，j，q三個(gè)節(jié)點(diǎn)為不同的節(jié)點(diǎn)；b中i，q兩點(diǎn)為相同節(jié)點(diǎn)，j為獨(dú)立的節(jié)點(diǎn)；c中j，q為相同的節(jié)點(diǎn)，i為獨(dú)立的節(jié)點(diǎn)；d中i，j，q三個(gè)節(jié)點(diǎn)為相同的節(jié)點(diǎn)。表1給出了情況3）子樹合并與i，j，q節(jié)點(diǎn)之間關(guān)系的映射。

表1 合并方式映射關(guān)系

接下來，我們只需確定i，j，q三個(gè)節(jié)點(diǎn)的關(guān)系即可判定出子樹合并方式。由于序貫合并過程中滿足每次選擇的子樹對{i,j}均為最相關(guān)子樹，則結(jié)合定理2，可得合并點(diǎn)q的等價(jià)定義：設(shè)左右子樹的葉子節(jié)點(diǎn)集合分別為K，L，?k∈K，?l∈L，滿足a(k,l)=q。則可得節(jié)點(diǎn)q對應(yīng)的葉子節(jié)點(diǎn)相關(guān)性集合為C=｛,a(k,l)＝q；k∈K；l∈L}。i,j對應(yīng)的葉子節(jié)點(diǎn)相關(guān)性集合分別為A=｛,a(m,n)＝i；m,n∈K;m≠n}，B=｛,a(u,v)＝j(luò)；u,v∈L;u≠v}。由推論1，我們可知，通過比較集合A，B，C的均值即可判定i，j，q三個(gè)節(jié)點(diǎn)的關(guān)系，進(jìn)而根據(jù)表1中的映射關(guān)系獲得子樹的合并方式。

我們采用廣義似然比的方法比較集合A，B，C的均值。

由于對于原始待推斷樹狀拓?fù)?，其葉子節(jié)點(diǎn)之間相關(guān)性的相對大小關(guān)系是確定的（因?yàn)橐獫M足單調(diào)性和一致性），那么在理想情況下葉子節(jié)點(diǎn)相關(guān)性的測量值的相對大小也滿足此確定關(guān)系，因此，只要保證推斷出的樹狀拓?fù)渲杏扇~子節(jié)點(diǎn)共享鏈路長度表征的葉子節(jié)點(diǎn)相關(guān)性的相對大小關(guān)系，與實(shí)際中測得的葉子節(jié)點(diǎn)相關(guān)性的測量值的相對大小關(guān)系一致，即可認(rèn)為推斷出的拓?fù)渚褪谴茢嗟耐負(fù)?。分析我們的推斷過程，由于使用最相關(guān)子樹合并，因此在推斷過程中保證了相關(guān)性測量值較大的葉子節(jié)點(diǎn)之間的共享鏈路長度大于相關(guān)性測量值較小的葉子節(jié)點(diǎn)之間的共享鏈路長度，且合并過程中使用了合適的合并方式，保證了共享鏈路長度相等的葉子節(jié)點(diǎn)有相同的公共父節(jié)點(diǎn)，那么我們可得由最相關(guān)子樹合并方法推斷出的保留了葉子節(jié)點(diǎn)相關(guān)性的相對大小關(guān)系，其推斷出的拓?fù)渚褪窃纪負(fù)?。（未完待續(xù)）

[1] DONNET D,FRIEDMAN T.Internet topology discovery:a survey[J].IEEE Communications Surveys and Tutorials,2007,9(4):2-15.

[2] ZHANG X,CHRIS P.A survey on selective routing topology inference through active probing[J].IEEE Communications Surveys &Tutorials,2012,14(4):1129-1141.

[3] 姜譽(yù)，方濱興，胡銘曾．．大型ISP網(wǎng)絡(luò)拓?fù)涠帱c(diǎn)測量及其特征分析實(shí)例[J]．軟件學(xué)報(bào)，2005,16(5):846-856

[4] COATES M,HERO A III,NOWAK R,YU B.Internet tomography[J].IEEE Signal Process Magazine,2002,19(3):47-65.

[5] 趙洪華，陳鳴．基于網(wǎng)絡(luò)層析成像技術(shù)的拓?fù)渫茢郲J]．軟件學(xué)報(bào)，2010,21(1):133-146

[6] DUFFIELD N,PRESTI F.Network tomography from measured end-to-end delay covariance[J].IEEE/ACM Transactions on Networking,2004,12(6):978-992.

[7] 李勇軍，蔡皖東，王偉．基于端到端報(bào)文丟失的網(wǎng)絡(luò)拓?fù)渫茰y算法研究[J]．通信學(xué)報(bào)，2007,28(10):85-91

[8] SHIH M F,HERO A.Hierarchical inference of unicast network topologies based on end to end measurements[J].IEEE Transactions on Signal Processing,2007,55(5):1708-1718.

[9] CASTRO R,COATES M.,NOWAK R.Likelihood based hierarchical clustering[J].IEEE Transactons on Signal Processing,2004,52(8):2308-2321.

[10] NI J,XIE H,TATIKONDA S.Efficient and dynamic routing topology inference from end-to-end measurements[J].IEEE/ACM Transactions on Networking,2010,18(1):123-135.

[11] ERIKSSON B,DASARATHY G,BARFORD P.Efficient network tomography for internet topology discovery[J].IEEE/ACM Transactions on Networking,2012,20(3):931-943.

[12] FEI G,HU G.Improving maximum-likelihood-based topology inference by sequentially inserting leaf nodes[J].IET Communications,2011,5(15):2221-2230.

[13] 費(fèi)高雷．基于單播端到端測量的網(wǎng)絡(luò)性能參數(shù)估計(jì)方法研究[D]．成都：電子科技大學(xué)博士學(xué)位論文，2012

[14] 楊京禮，姜守達(dá)，魏長安，孫超．一種高效的單播網(wǎng)絡(luò)自適應(yīng)拓?fù)渫茰y算法[J]．電子學(xué)報(bào)，2013,41(10):1888-1894

[15] HENRY S,JOHN W W.Probability,Statistics,and random processes for engineers(fourth edtion)[M].New Jersey:Pearson Education Inc,2011.

[16] 現(xiàn)代數(shù)學(xué)手冊．隨機(jī)數(shù)學(xué)卷[M]．武漢：華中科技大學(xué)出版社，2000

[17] 周勇，馬昀蓓，謝尚宇，王曉靖．理工科概率統(tǒng)計(jì)（原書第8版）[M]．北京：機(jī)械工業(yè)出版社，2009

[18] 饒?jiān)迫A，曹陽，楊艷，吳銳．基于Pareto分布的IP骨干節(jié)點(diǎn)輸入通信量模型[J]．計(jì)算機(jī)科學(xué)，2006,33(3):27-28

10.3969/J.ISSN.1672-7274.2016.05.011

TN911 文獻(xiàn)標(biāo)示碼：A

1672-7274（2016）05-0036-04