设备网络延时是什么意思

第27卷第7期20()7年7月计算机应用ComputerAp成cationsVol.
27No.
7July2007文章编号:1001一9081(2(X)7)07一1569一03网络中设备位置问题分析谢铁铮,·2(1.
中国科学院计算技术研究所,北京10(X)80;2.
中国科学院研究生院,北京1以X碎9)(扭汉jeZ(兀幻@9灿11.
com)摘要:通过引入虚拟的质量保证协议(SLA)服务条款,提出网络中形式化的设备位置问题,并根据网络特点改进了现有的静态局部优化算法,证明了在常见的分区低服务质量敏感类型的k-median问题和低服务质量敏感类型的U几问题中的近似度上界.
测试结果表明改进后的算法在较小增加现有静态算法近似度的情况下运算速度有较大的提高.
关键词:设备位置问题;网络;服务质量保证协议;近似度中图分类号:T刃93文献标志码:AAnaiysisoffaciIitylocationinnetworkxIETie一zhengl·2(1.
乃砧'众吻of肠呷taerTechnD城拼chineseAC山龙m少of&icnces,2.
'阳以功侧阳&爪"几ch￡nes.
注c山众衅of反icnc曰,及访ngBe乒ngl《X又)80,C人￡na;1以X妈9,Chi呵Abstract二WheretoPutserversinnetw0Iktolocationproblem.
吸eproble二wasforlllalized场providedefiningmoreeffective.
旧erVICeserneetoel]旧torleve】ag陀ementcanbedass击edas血cilitycustome瓜肠enolm公loc吐se二h司gorithmlocalitygapofK一田州五an以gotithmofp师tioninataticproblemwasmod笛ed石劝moneateP(SLA)betweenfacilitiesandto幻禅Otofitthenetwork.
Thelowserwcequ心tyse州ceandincaPacitatedfacilitylocationProblemoffow叱州ceq斑山tyse州cew二poiniedout.
Thetestresulte日howthattheslgotithmeanreducethe二putationtimee任eCtively袱thaliulerisingoflocalltygap.
Keywords:facilitylocation四blem;network;Se川ce玩vel灰尹emeni(SLA);localltygap0引言在给定设备集合F,客户集合c,以.
FVcjoc(d认,cj)o2+),表示关设备为ci客户提供服务的费用,选择一定的设备使得为所有客户提供服务的费用最小称为设备问题.
根据d的特性可分为一般距离、M丽c空间和欧氏空间问题.
选择最多k个设备为所有客户提供服务并使服务费用最小的问题被称为k一m翻ian问题.
设定开设设备集合需要一定花费,求解开设设备集合为所有客户提供服务并使服务费用最小的问题被称为无容量限制设备位置(UncaP翻tatedFacility城ation,UFL)问题.
在设定设备容量情况下求解相应问题被称为有容量限制设备位置(capacitat曰Facility城ation,C几)问题,如果同时设定设备数上限无,则被称为k一C几问题.
集合覆盖问题可以归约为k一二dian问题,即这类问题是NP一Haxd问题.
求解这类问题的最优解常见的算法是线性规划法〔'一7J或局部搜索法,丁uJ.
vijay柳.
等人〔131在总结以上近似算法的基础上对Me示c空间的设备位置问题给出了近似度为3+2/P的k一median算法、近似度为3的U几算法和近似度为4的ao一C几算法是目前较好的局部优化算法.
本文主要针对网络应用的设备位置问题,通过引人虚拟的服务质量保证协议(SerVice玩velAgreement,SLA)条款将不稳的网络延时设备位置问题转化为一个常量服务费用设备位置问题,在对网络中的设备位置问题所应具备的特点进行分析后对vijay算法进行了改进,并分析了其对常见的低服务质量敏感和分区低服务质量敏感类型的应用情况下的局部最优解上界.
在针对vijay算法的比较测试结果中表明本算法在增加较小的近似度的情况下具有较快的速度.
1网络中的设备位置问题1.
1网络中设备问题算法特点设备位置问题在网络中有着重要的应用,通过设备位置问题的求解可将服务器放置在更为合理的网络位置从而为用户提供更好的服务.
在大型网络环境下求解设备问题时需要注意网络的弱藕合性和动态性.
由于网络中不断有新的计算机加人和退出,因此牺牲部分性能从而提高速度以便更快地适应新的网络环境是网络中位置问题的关键,由于采用线性规划方法当网络条件变化时需要完全重新计算相应的设备位置,因此线性规划方法仅适用于小型固定的静态网络条件下,或者统计意义上的静态网络条件下的设备位置分析.
局部搜索法由于可以将原有局部最优解作为初始条件进行计算因此更适合在动态性强的实际网络中应用.
由于网络中节点数量较大,因此一般而言不存在完全了解整个网络条件的节点进行设备计算,同时相应的服务费用具体值的获取需要消耗相应的通信量和通信时间,因此网络中的设备问题不同于静态条件下求解设备问题,如何利用局收稿日期:2叨7一01一10;修回日期二2加7一05一140作者简介:谢铁铮(1977一),男,福建泉州人,博士研究生,主要研究方向:高性能算法、网格服务部署.
1570计算机应用2007年部数据进行计算以降低空间复杂度以及如何利用节点间一般数据交换降低通信量是网络中设备问题算法设计的关键.
同时由于网络节点数量巨大,虽然相关的局部搜索算法时间复杂度是多项式级别的,但也需要利用整个网络的并行特性和其他特性减少计算时间.
1.
2网络延时作为服务费用的设备问题设网络节点构成图C(V,E),.
住E表示所连接的节点间延时,设任意两点间延时为D("',竹).
为寻找合适的位置为所有用户提供总体上满意的服务,需要各个用户到相应的服务节点间延时之和最小,即求解设备位置问题FoV,C.
V,V关.
FVcjoc(d吠,cj)二D",Cj)).
根据网络中节点间访问的路由方式可知,任意两个节点间的访问延时由任意两点间的最短路径构成,根据图中最短路的定义可知图中任意两节点间的距离满足三角不等式:V,',马,竹任V,D(叭,竹)c二x表示服务响应时间,c'表示不同的响应时间分段值(2),a'是不'邢二今马2网络中设备位置问题算法分析2.
1算法改进分析设5表示算法的局部最优解,口表示算法的全局最优解,S'二(5认)uB表示5的某一个相邻解,其中AcS,BcF\S,根据具体的设备问题,A,B需要满足一定的条件,例如在k一median问题中需要满足IAI==I引十1,.
(.
(·川,由容麻酮毗燃燃存在,将式(4)所有k个交换不等式相加可得:coat,'"',.
,.
柔,(,》"a'·',·,'·cost,'"''.
cos'.
(0)+costj(0)(5)同样,对应上一交换对子问题,,p,添加相应的设备,并将式(3}所产生的k个不等式相加可得:cos'·(5)',~.
',、琴,.
,_',、("(.
(")".
,3、一,.
"5、一'尹一,、一,,c'))+,蓦.
'),.
(二,,.
蔫.
',二.
(,〕.
蓦.
',,.
(,)蔫,),'、((d(.
'(c'),(d(.
:(c'),c'))+costj(0)'c'))+(d(,,(几),c'))+操作.
首先考虑单个交换问题,设op.
(劝二S/lxlul川,则:伽tP'op·'·,'==cos!
",一二乌二,"'一"'.
'奚,,'d',,一,,.
'8,由局部最优解条件可知costP(oP.
(x))>cos《5),作交换a::、0(ao5,.
.
0),满足条件}几(5)np口(.
(5))!
>士lp口(.
(!
))!
,将所有'个交换不等式相加可得:cos:'",',.
,.
,.
,弄.
,.
(.
(二,)"'口·'价',一"+一,.
.
弄,口(.
',〕)"(.
.
(.
'),.
'))+一.
￡.
界,口(.
、二》,"(『.
(·'),.
(二)))二cos,'0,+('一十)、""(1+(卜十抽)Cos:(0)'9,对于P交换问题,根据类似上面的推导过程可得cos'(5)'('+(,一令).
)cos'(0).
3测试结果首先我们对算法对vijay算法的平均近似度进行了测试,测试问题集由inet3.
0生成的网络拓扑产生.
"'几(".
哪习(1+(1一李、、.
cos'_(0、十c.
,,(0、(6)\''\'k)1'.
,一.
、,,··~.
,、V,2.
3分区低服务质盘敏感设备位置问题在一些服务质量敏感的应用中,由于距离产生了较大的网络延时,从而使得跨越区域提供服务产生了很大的延时.
目前内容传送网络(ConteniDelive守Netwo浅,CDN)等模式的网络优化方法通过在不同的地理位置设置镜像服务器提高服务质量,在用户访问同一区域内的服务时能够获得满意的服务,而跨区访问时则服务质量很差.
若设L表示网络中的不同区域,0:,、l(,.
V,1oL)表示节点到区域的映射,则可将条件形式化为设备位置问题满足:Vc'已cV关,石任F(0"),e(c')ande铸)==e(c').
d",c')》d(石,.
'))(7)同时对Vc'.
c以,石.
F(0以)二e(c')),.
=d.
/蠕值较小.
此类问题一般为k)ILI的k一m心皿问题.
一般情况下总是在每一个区域设置至少一个服务节点,而我们可以证明对于初始设备集合包含所有区域时,最后所得的局部最优设备集必然包含所有区域,即:对VS(VIoL(日:.
5(0(:)二1))),VS,.
{5'.
承(5)and(日1oLV,.
5佃(:)尹1川,有肠3:(5,))肠Jt(S),根据式(7)这一结果易于证明.
因此此问题可以变成一个对各个区域内的低服务质量敏感的k一me山an问题.
在k一median问题中只存在设备的交换1.
071.
肠1乃5L以L03L021一01l0.
990.
98决产代才七理声/介沙尸一一,扩沪2七尹刁卜材矛夕产兰三圃'叫卜-k二3,叫.
一k二5一奋一k=8一刁略一k=10图Ik叨司ian问题基于Vijay算法近似度图中纵轴为设备问题为Vijay算法计算所得肠Jt(s)与本算法计算所得.
以(5)值之比,横轴为.
值.
从图中看出,随着.
,希值的增加近似度逐渐增加.
UFL问题求解结果近似度类似于k一median算法结果;同时本算法的计算时间比vijay算法的计算时间减少20%.
因此本算法可以看作简化的快速局部优化算法,考虑到其并行可能性以及计算过程涉及数据仅限于有请求相关性的设备与用户间,本算法更利于在网络中实现.
4结语本文针对网络条件下的设备问题求解提出了采用SLA惩罚函数作为设备问题服务费用从而将不稳定的网络延时常量化为对应的服务费用.
在基于网络中设备问题所应具备的特点的基础上,改进了Vijay算法,并对低服务敏感应用和分区低服务敏感应用类型的UFL和k一m曰ian问题给出了其局部最优解的上界.
实验结果表明本算法具有一定的价值.
(下转第1575页)第7期廖传书等:无线传感网络的冲突感知MAC协议研究1575种协议的能量消耗比较.
如表1中的仿真环境设置,三种协议的节点的发送和接收能量设置相同.
如图4所示,在节点稀疏的环境下,由于节点间数据流量较小,产生冲突的概率较小,cAMAC协议和sMAC、802.
n相比冲突避免的优势不大,所以CAMAC协议的能量消耗相对于SMAC和802.
11的优势并不明显.
如图5、图6所示,在节点密度较大的环境内,由于节点密度大,节点间数据流量增大,冲突的概率增大,数据帧丢失、重传的概率增大,此时CAMAC协议的冲突避免优势充分体现出来.
避免了节点间不必要的冲突,减少了数据重传的次数,降低了节点的能量消耗,因而其能耗优势也体现出来.
从图中可以看出,节点密度越大,CAMAC相对于其他两种MAC协议节省的能量越多,其优势越明显.
1以洲】990蝴970卿蝴940930920乏熟巴吕山910侧月】050100150200Tin回.
图650个节点条件下的能耗5结语无线传感网络是事件驱动的网络,冲突感知的CAMAC协议,通过在竞争窗口内为节点选择发送时槽和进行功率控制,有效地避免了同一事件触发的同源冲突和不同事件触发二二二二二二二二二二二二二二二之(上接第1571页)参考文献:[1]SHMOYSD,TARI)OSE.
AARDALK.
APP功万imationalgorithmsforfaCilityloca6onP功blemsICI//Roc以月in,试the29thAnnual人CMSym,拍iumonTheory过肠mPuting.
目Paso,SanDie卧Califonli'ACM巧翻5.
1997:265一274.
12]CllARIKAM,GUHAS,TARI)OSE,'以Aconslant毛沈tor伞p均石mation目9丽thmforthek一田曰ianP功blemlc]//乃"比司in夕ofthe3lstAnnu日ACMS,m脚siumon仆即叮ofCOmpu6咯.
5田1氏e-即,C山肠mia二ACMPr幽,1999:129一149.
13]CHARIKARM,GUHAS.
】切p功v记即切七1几atodalal即rithm.
forthe阮ility10日吐ionandk一m曰1,P汕lemB【c]//Pr能eedin,ofthe40th人朋udsym帅nilnoFo"ndati皿ofComPuterscieo.
NewY诫:IEEEComPutersx二iety,1999:378一388.
【4】CHUDAKF.
ImProv己叩p功刀ma石on公即对d加.
foruncaPacilatd阮ilityloCationProblemlC]//P阴eedingofthe6thCo刊re茂nceonInte脚而,朋面ngandConlbi朋torial伽ti而.
tion,Houaton,Te翔,UsA,June22一24,1998.
L祖don,UK:SP6n脚·V翻峪1998:180一194.
【5]CHUDAKF,SHMOYSD.
】mp功v曰即pm范诩6onal四rith血for以甲配itat记阮ilitylocationP功blemlC]//氏oc以刃ing试thelothAnnualACM一SIAMSynIP阅iumonDISC代te川90幼thms.
Bal6m二,USA:ACM巧.
5,1999:875一886.
I6lCUHAS,KHULLERS.
Cr价泪ys示kesback:lmP功v曰faCilitylO-cation司90'thms[cl//PrOC创泪'n,oftheg,hAnnualAcM一5认梦5帅衅inmon川阳爬比川9面th、.
Neworleans:ACM阮55,1998:649一657.
的非同源冲突,减少了由于冲突造成的丢包、重传的概率,有效地节省了无线传感节点宝贵的能量.
参考文献:【llYEW,HEIDD均仆俐J,ESllllND.
灿国旧留,幽d时MAC户成1记七讯旧.
.
伙加砚btq刀R仪践浦哪JZlatln恤rn函.
过为加卜以」d址C.
Ife~.
】E王:EQ加例姗山司Q加皿面画.
5祀1硒es(IN-R兀OM龙m).
冷,Y伪人:正EEQ叨PU妞阮1肉,加田.
[21VanDAMT,LANGENDOENK.
如ad叩'veene叮一心cientMACp州OColfor初比1翎~【c]刀乃仙笼曰in乎oflstlnterr.
户石on司CO刊re花nceonEmh妇d曰NetW0rkedsenSOrsyste,(阮nsys2(X)3).
1加灿seles,CA:ACMPre阳,2加3:171一180.
13]GOMEZJ,CAMPBELLAT,NAGHSHINEHM,'al.
Con~9廿'胭missionlx附.
in衍以翎ad械耽饰.
击s[C]刀P阴.
泪in,试the9thIntema6onalCoI1ferenceonNetw切击n刚此日日(ICN阳1).
Was枯n咨on,Dc:IEEEC0mPu姗5祀ietyl玩55,2(X)卜24一34.
【41MUQATTASHA,KR叨忆M.
A幼叼e-c坛训阴lsoluti二fortr山1日而,幼.
lx"喇,阴七日in俪曰essadh叱n改版吐.
【q刀R仪找走卿JthaACMM山iH0c丫冲.
几甲生妞1乡,」叩阴:【8.
n.
】,2以拜:210一22L[51BHARGHAyANV,DEMERSA,SHENKERS,d武MACA:Am汕a一p功tOColfor初代le8SLAN'.
【J].
PrDCeediu,ofAcMSIGCOMM,1994,24(4):212一225.
16]KARNP.
MACA一An,cha朋el一meth记俪p朗ket、山.
【C]//ARR口CRRLAInateurR侧七ogthComputerNetworkingCon-免花nce.
助ndo盯二人RRL,19叭):134一140.
[7]扒MIESONK,BALAKRISHNANH,TAYYC.
Sift:aMACP功卜colforevent.
dri,en俪此lessse~networks,Mrr-优5.
TR名94[R].
UsA:初rr,2加3.
[8]MONKSJP,BIJARGHAVANV,WMWHWU.
毛侧朋missi,pqw-er二园formultiple二,初代1.
PacketnetW0rk.
【cl//PrO-c以刘In,oftheIEEEin丘沁omCo刊re花nce.
NJ:IEEEComnlu城ca-tions祀iety,2(X)1:219一228.
17lJ幻NK,VAZIRANIV.
洲mal刁u司即p拍石m川1oalg面th.
for功e苗c阮ility10山幼ionandk一m.
山anp汕1二slc]//p阴以月in,成th.
4OthAnn回Sylll娜ium.
Foundati.
'Computersci,ce·NewY诫:IEEEC0mputerS笼iety.
1999:1一10·【8〕口舰刃AKF,确卫儿IA砚沃明D.
ln甲曰司即钾浦爪西on应洲山.
公份甲阴"川曰公'山ty】oc西二P油1,【q刀岛叩,曲娜过此7tbQ刘油'二.
1ot曰匆留巧粤朋耐昭.
日0"由访址丽习勺1而左面叭C呱人.
侧叹加neg一n.
1望为.
【5,1.
】:知dng沈11哪晓1田一1叭[glKANUNGOT,MOUNTD,NETANYAHUN,'aLAloc习~h即PID刀.
tional,rithmfor卜.
clusterin以cj刀R优曰泪in,菌the18thAnnual人CMSym卿iuoonComPutati.
阔G阳me匀·York:ACMPI吧55,2加2二10一18.
110lPALM,TARDOSE.
WEXLERT.
F鱿ditylOCa'on衍thn.
uni-肠m卜田心叨paci石.
[C]//Pr优e曰五卿Ofthe42ndAunuallEEE5卿卿」u.
,Found如.
面CDmpoter趾1即ce.
l朋V绍",Ne-姐d'USA:IEEEP~,2(X)1:329一338.
[11]KORU阳LUM,PLAxTONC,R人」ARAMANR.
Analysis试alo-司二hheuri吐icforfaCility1OCationProblemslC]//乃议"闭in朗ofthegthAnnudACM一认MSym娜iumon}阴比te灿,"thlns.
N眯众leans:ACM乃翻5,1998:1一10.
112]KORuPULUM,P曰以TONC,RAJARAMANR.
Analysisofa卜司~hheu行拓cfor血ilityl.
山鱿ionl朋blems,Tec俪山Report98召olRI.
DIMACS,1998.
113]ARYAV,GARGN,KHANDEKARR,已成】J兄习二hh砚1"5-ticsfork一m.
五二胡d血'ilitylocationprDblems【C】刀JEFFREYV·P欧忱劝卿Jthe33记A二耐人CMS帅娜iumonTheO口试C,-puting.
H.
二1O805,C~:ACMP沈sa,2(X)1:21一加.