非對(duì)稱網(wǎng)絡(luò)單向時(shí)延的最小范數(shù)估計(jì)

賈巧伶，高 勇

（四川大學(xué) 電子信息學(xué)院，四川 成都 610064）

0 引言

近年來，通信組網(wǎng)的發(fā)展成為一種趨勢(shì)，網(wǎng)絡(luò)性能的測(cè)量也越來越受到重視，而單向時(shí)延是評(píng)價(jià)通信網(wǎng)絡(luò)性能的重要指標(biāo)之一。單向時(shí)延是指數(shù)據(jù)包從發(fā)送端經(jīng)由網(wǎng)絡(luò)到達(dá)接收端所需的時(shí)間。往返時(shí)延(RTT,Round Trip Time)常被用作一種估計(jì)方法，它是記錄數(shù)據(jù)包從發(fā)送端經(jīng)通信網(wǎng)絡(luò)到達(dá)接收端然后再返回發(fā)送端所需要的總時(shí)間，因此，單向時(shí)延可由RTT時(shí)延除以二均分得到。但是由于通信網(wǎng)絡(luò)的非稱性，這種估計(jì)方法并不準(zhǔn)確。所以，常用的測(cè)量方法是分別記錄數(shù)據(jù)包發(fā)送時(shí)間和到達(dá)時(shí)間，但是由于收發(fā)兩端主機(jī)的時(shí)鐘運(yùn)行并不同步，從而導(dǎo)致了單向延時(shí)測(cè)量的不準(zhǔn)確性。

當(dāng)然，理想的方法是同步所有測(cè)量主機(jī)的時(shí)鐘。GPS全球定位系統(tǒng)可以提供高精度的硬件時(shí)鐘同步[1-2]，但是其價(jià)格及其昂貴，不利于一般的工程應(yīng)用。因此，很多學(xué)者利用軟件方法對(duì)時(shí)鐘的同步算法進(jìn)行了深入的研究，先后提出了點(diǎn)線垂直距離最小算法、曲線和線間最小面積算法、模糊聚類算法[3-5]等，這些算法都是為了消除時(shí)鐘時(shí)滯和時(shí)鐘偏差以獲得高精度的時(shí)鐘同步補(bǔ)償。

區(qū)別于解決時(shí)鐘不同步帶來的問題，文獻(xiàn)[6]提出了一種不需要時(shí)鐘同步的單向時(shí)延測(cè)量方法，利用 Windows平臺(tái)下提供的高精度性能計(jì)數(shù)器，建立兩主機(jī)的性能計(jì)數(shù)器相對(duì)模型，推導(dǎo)出通信網(wǎng)絡(luò)單向時(shí)延表達(dá)式，但是使用對(duì)包理論對(duì)待定項(xiàng)的更新有時(shí)會(huì)偏離正常水平，這將導(dǎo)致測(cè)得的單向時(shí)延波動(dòng)范圍較大。基于文獻(xiàn)[6]中存在的問題，本文簡(jiǎn)化了實(shí)驗(yàn)仿真模型，不需要估計(jì)更新待定項(xiàng)，利用最小范數(shù)法對(duì)文獻(xiàn)[6]中所建表達(dá)式進(jìn)行處理，獲得的單向時(shí)延波動(dòng)范圍更小,更準(zhǔn)確。這種方法不需要兩主機(jī)間的時(shí)鐘同步，不僅適用于非對(duì)稱通信網(wǎng)絡(luò)，并且具有在線測(cè)量、高精度、低復(fù)雜度的優(yōu)點(diǎn)。

1 模型建立

在Windows平臺(tái)下有一個(gè)可以提供微秒級(jí)計(jì)數(shù)的高精度性能計(jì)數(shù)器，我們可以建立兩主機(jī)間的性能計(jì)數(shù)器相對(duì)模型，推導(dǎo)出網(wǎng)絡(luò)單向時(shí)延表達(dá)式[6]。

首先建立主機(jī)S和主機(jī)C的性能計(jì)數(shù)器相對(duì)模型，如圖1所示。

圖1 兩主機(jī)的性能計(jì)數(shù)器相對(duì)模型

所以式(3)可寫為：

注意到在Windows平臺(tái)下，使用QueryPerformance Frequency()和 Query Performance Counter()函數(shù)[7]可獲得機(jī)器內(nèi)部定時(shí)器的時(shí)鐘頻率和計(jì)數(shù)，從而實(shí)現(xiàn)μs級(jí)的準(zhǔn)確定時(shí)，但是根據(jù)文獻(xiàn)[7]中所述性能計(jì)數(shù)器的取值有時(shí)會(huì)意外向前跳躍，但是從一次意外跳躍到下一次意外跳躍這段時(shí)間內(nèi)，fs、 fc、均保持不變，因此，可以將q看作一個(gè)常量，由式(4)建立了兩主機(jī)間的相對(duì)模型表達(dá)式。

2 算法推導(dǎo)

如圖2所示，兩主機(jī)建立TCP連接，主機(jī)S以周期間隔向主機(jī)C發(fā)送UDP數(shù)據(jù)包，記主機(jī)S發(fā)送第i個(gè)數(shù)據(jù)包時(shí)的性能計(jì)數(shù)器的值為，記主機(jī) C在接受到第i個(gè)數(shù)據(jù)包時(shí)的性能計(jì)數(shù)器的值為()。

圖2 單向時(shí)延發(fā)包模型

根據(jù)單向時(shí)延發(fā)包模型建立的仿真模型如圖3，在主機(jī)S和主機(jī)C間建立TCP連接，主機(jī)S向主機(jī)C發(fā)送數(shù)據(jù)包，發(fā)送時(shí)記錄主機(jī)S的性能計(jì)數(shù)器為1,iR，并且在主機(jī)C接收到數(shù)據(jù)包時(shí)記錄其性能計(jì)數(shù)器的值為2,iR，主機(jī)C接收到數(shù)據(jù)包后立即發(fā)送回?cái)?shù)據(jù)包，此時(shí)性能計(jì)數(shù)器的取值為3,iR，在主機(jī)S接收到返回的數(shù)據(jù)包時(shí)其性能計(jì)數(shù)器的取值為4,iR 。

圖3 單向時(shí)延仿真模型

由式(6)、式(7)可知，該線性方程組的未知數(shù)多于方程個(gè)數(shù)，2個(gè)方程式，3個(gè)未知數(shù)q，其中可分別調(diào)用Que- ry Performance Frequency()和 Query Performance Cou-nter()函數(shù)獲得[7]，因此該線性方程為欠定方程。

舉一個(gè)簡(jiǎn)單的例子來說明欠定線性方程組的解，假定線性代數(shù)方程為：

如圖 4所示，直線 x1+2x2=10上的所有點(diǎn)(x1,x2)都是方程的解。如果想得到唯一的解，必須加一個(gè)約束條件。將解x的范數(shù)最小作為約束條件，這樣得到的唯一解為最小范數(shù)解。x的范數(shù)最小相當(dāng)于向量x的端點(diǎn)到原點(diǎn)的距離最小，所以最小范數(shù)解又稱為最短距離解。

圖4 欠定方程式(8)的解

對(duì)于式(8)的最小范數(shù)解，就是與原點(diǎn)距離最短的解，即為圖4中所示坐標(biāo)(2,4)的點(diǎn)。

更一般的，設(shè) X0=Gb 為欠定方程組 A X= b 的最小范數(shù)解，則 X0為欠定方程組所有解中范數(shù)最小的解，即：

欠定方程的最小范數(shù)解為[9]：

其中G為A的右偽逆矩陣，即：

其中I為單位矩陣。

因此利用上述理論，在建立2臺(tái)主機(jī)TCP連接的情況下，主機(jī)S向主機(jī)C周期的發(fā)送數(shù)據(jù)包，主機(jī)C接收到數(shù)據(jù)包后立即向主機(jī)S發(fā)回?cái)?shù)據(jù)包，可根據(jù)最近一次的性能計(jì)數(shù)器取值，結(jié)合式(6)、式(7)估計(jì)出上下行單向時(shí)延

3 仿真結(jié)果及分析

在第三代移動(dòng)通信標(biāo)準(zhǔn)CDMA2000無線通信網(wǎng)絡(luò)狀態(tài)下，通過兩塊無線上網(wǎng)卡實(shí)現(xiàn)網(wǎng)絡(luò)互連，網(wǎng)絡(luò)帶寬為3.1 Mb/s，獲得一組實(shí)驗(yàn)數(shù)據(jù)，如圖5所示。

圖5 無線網(wǎng)中兩主機(jī)時(shí)延

圖5(e)是往返時(shí)延RTT的均分，即上下行時(shí)延相等，可看出無線通信網(wǎng)絡(luò)受到干擾大，時(shí)延波動(dòng)性也很大；其中，圖5(a)、圖5 (b)是使用本文中所述的最小范數(shù)估計(jì)法獲得的上下行時(shí)延，圖 5(c)、圖 5 (d)是使用文獻(xiàn)[6]中的對(duì)包方法估計(jì)的上下行時(shí)延，它們都體現(xiàn)了通信網(wǎng)絡(luò)的非對(duì)稱性，并且主機(jī)S到主機(jī)C的上行時(shí)延平均水平要大于主機(jī)C到主機(jī)S的下行時(shí)延平均水平，這是因?yàn)閷?duì)于實(shí)際網(wǎng)絡(luò)來說，上行網(wǎng)絡(luò)平均帶寬要小于下行網(wǎng)絡(luò)平均帶寬。從圖5中可以看出由于使用對(duì)包方法在定時(shí)更新待定項(xiàng)時(shí)會(huì)偏離正常水平，導(dǎo)致所得結(jié)果波動(dòng)范圍很大，而使用最小范數(shù)法估計(jì)的時(shí)延比用對(duì)包法獲得的時(shí)延更精確，波動(dòng)性更小，減小了使用對(duì)包方法中極大（或極小）尖峰值的出現(xiàn)。

4 結(jié)語

本文利用Windows平臺(tái)下提供的微秒級(jí)計(jì)數(shù)的高精度性能計(jì)數(shù)器構(gòu)建了仿真模型，通過搭建平臺(tái)建立兩主機(jī)間的TCP連接，根據(jù)所得數(shù)據(jù)建立數(shù)學(xué)表達(dá)式，利用最小范數(shù)估計(jì)法獲得單向時(shí)延，經(jīng)過實(shí)驗(yàn)驗(yàn)證本文方法比使用對(duì)包方法得到的結(jié)果波動(dòng)性更小，更精確，并且只需根據(jù)最近一次的性能計(jì)數(shù)器取值就能更好的跟蹤性能計(jì)數(shù)器數(shù)據(jù)的變化以及時(shí)反映網(wǎng)絡(luò)時(shí)延的變化，具有可在線測(cè)量、精度高、不需要時(shí)鐘同步和適用于下一代互聯(lián)網(wǎng)通信[10]的優(yōu)點(diǎn)。

[1] 胡志堅(jiān),張承學(xué),杜志偉.基于 GPS的同步時(shí)鐘的研制及其應(yīng)用[J].小型微型計(jì)算機(jī)系統(tǒng)，2005,26(8):14 33-1435.

[2] 秦明偉，姚遠(yuǎn)程，李云.網(wǎng)絡(luò)時(shí)延測(cè)量中的時(shí)間同步系統(tǒng)應(yīng)用研究[J].通信技術(shù)，2008,41(08):149-153.

[3] 聶玉婷,高仲合.單向時(shí)延測(cè)量中的時(shí)間同步問題[J].通信技術(shù)，2009, 42(10):125-127.

[4] 王卓，朱德森，汪秉文.單向時(shí)延測(cè)量的實(shí)時(shí)時(shí)鐘同步算法[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2008,36(02):22-25.

[5] 王洪波,林宇,金躍輝,等.一個(gè)消除單向時(shí)延測(cè)量 中 時(shí)鐘頻差和時(shí)鐘重置的新方法[J].電子學(xué)報(bào)，2005:584-589.

[6] 秦張淼,周衛(wèi)紅,薛競(jìng)翔.基于高精度性能計(jì)數(shù)器的網(wǎng)絡(luò)單向時(shí)延研究[J].小微型計(jì)算機(jī)系統(tǒng)，2010,5(05):912-915.

[7] Microsoft Corporation. Query Performance Frequency function[EB/OL].(2005-01-09)[2011-11-05].http://msdn.microsoftcom/en-us/library/ms644905(VS.85).

[8] 周金森. 廣義逆矩陣與線性方程組的解[J].漳州職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006,8(02):15-17.

[9] 張崢嶸,嚴(yán)濤. 關(guān)于線性方程組 Ax=b的解的注記[J].南京師大學(xué)報(bào):自然科學(xué)版，2001,24(01):21-24.

[10] 于溯，下一代互聯(lián)網(wǎng)廣域網(wǎng)接入研究[J].信息安全與通信保密，2011(10):65-68.