地址贝尔金无线路由器

第18卷第7期系系系系统统统统仿仿仿仿真真真真学学学学报报报报Vol.
18No.
72006年7月JournalofSystemSimulationJuly,20061930无线传感器网络低功耗混合地址编码算法无线传感器网络低功耗混合地址编码算法无线传感器网络低功耗混合地址编码算法无线传感器网络低功耗混合地址编码算法蔡一兵1,2李海波1王春峰1陈沫1李忠诚11.
中国科学院计算技术研究所信息网络室北京1000802.
中国科学院研究生院北京100080摘摘摘摘要要要要无线传感器网络低功耗MAC地址编码设计需要综合考虑地址通信能量开销地址编码容量不同地址类型支持等因素的影响首先分析了现有定长地址编码和哈夫曼地址编码算法的优缺点给出了地址编码性能评估参数给出了地址编码性能评估参数给出了地址编码性能评估参数给出了地址编码性能评估参数接着提出了一种混合地址编码算法接着提出了一种混合地址编码算法接着提出了一种混合地址编码算法接着提出了一种混合地址编码算法仿真结果表明新算法融合了两种地址编码优点较好地满足了无线传感器网络低功耗MAC地址编码的设计要求关键词关键词关键词关键词无线传感器网络低功耗地址哈夫曼编码中图分类号中图分类号中图分类号中图分类号TP393.
04文献标识码文献标识码文献标识码文献标识码A文章编号文章编号文章编号文章编号1004-731X(2006)07-1930-05MethodofLowPowerMixingAddressCodinginWirelessSensorNetworksCAIYi-bing1,2,LIHai-bo1,WANGChun-feng1,CHENMo1,LIZhong-cheng1(1.
InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080,China2.
GraduateSchooloftheChineseAcademyofSciences,ChineseAcademyofSciences,Beijing100080,ChinaAbstract:ThedesignoflowpowerMACaddresscodinginwirelesssensornetworksmustconsidertheeffectoffollowingfactors,suchastheenergyconsumptionofaddresstransmission,thecapacityofaddresscodesandthesupportofdifferentaddresstypes.
TheadvantagesanddisadvantagesofcurrentmethodsoffixedsizecodingandHuffmanaddresscodingareanalyzed.
Amixingaddresscodingispresentedandtheperformanceparametersofaddresscodingareputforward.
ThesimulationresultsshowthatthenewmethodmergestheadvantagesoftwokindsofaddresscodingmethodandsatisfiesthedesignrequirementsoflowpowerMACaddresscodinginwirelesssensornetworks.
Keywords:wirelesssensornetworks;lowpower;address;Huffmancoding引引引引言言言言1无线传感器网络是由众多微小传感器节点通过无线多跳自组织方式构成的网络可实现物理世界计算世界以及人类社会的相互连通能量问题是传感器网络的核心问题之一[1]近几年来研究人员开始关注传感器网络低功耗地址机制研究如何减小地址长度以降低地址通信能量开销[2-5]文[5]利用无线多跳共享信道下MACMediumAccessControl地址空间复用特性提出分布式MAC地址按需分配算法和哈夫曼地址编码方法减小了地址编码长度有效降低了地址通信能量开销地址机制是信息网络设计的最基本问题一个实用的地址机制应综合考虑各种因素影响无线传感器网络节点能量有限减小地址编码长度及平均长度对延长节点及网络寿命非常重要这是无线传感器网络与其他网络的显著区别此外地址编码容量是否富余编码是否支持不同地址类型同样也不容忽略传统的定长地址编码在地址编码容量富余设收稿日期收稿日期收稿日期收稿日期2005-06-02修回日期修回日期修回日期修回日期2005-08-03基金项目基金项目基金项目基金项目国家自然科学基金60273021,中科院计算所青年创新基金2005660012作者简介作者简介作者简介作者简介蔡一兵蔡一兵蔡一兵蔡一兵1971男福建长汀人工程师博士生研究方向为无线自组织网络李海波李海波李海波李海波1984男河南周口市人硕博连读生研究方向为无线自组织网络王春峰王春峰王春峰王春峰1976男山东淄博人助研博士研究方向为QOS控制陈沫陈沫陈沫陈沫1981男江苏盐城人硕博连读生研究方向为无线自组织网络李忠诚李忠诚李忠诚李忠诚1961-男黑龙江哈尔滨人研究员博导研究方向为下一代网络计不同地址类型编码支持方面要比哈夫曼地址编码灵活哈夫曼地址编码的平均长度要小于定长地址编码但未考虑后面的因素影响了哈夫曼地址编码的实际应用本文首先介绍了无线传感器网络MAC地址编码的相关研究然后从无线传感器网络低功耗MAC地址编码要求出发对哈夫曼地址编码和定长地址编码的利弊进行了详细分析接着提出了一种低功耗混合地址编码算法给出了地址编码性能评估参数在此基础上对各种地址编码算法进行仿真性能比较仿真结果表明新算法融合了两种地址编码优点较好满足了无线传感器网络MAC地址编码要求1地址编码相关研究地址编码相关研究地址编码相关研究地址编码相关研究现有地址编码包括定长地址编码和哈夫曼地址编码为了方便目前传感器网络采用定长地址编码机制给节点静态配置在全球或全网范围内唯一的MAC地址地址编码长度由预计节点总数确定所有地址编码长度相同无线传感器节点电源能量极其有限很多情况下传感器节点数目众多并分散在条件恶劣的远程环境电池更换困难能量耗尽是传感器节点失效的主要原因通信能量开销是节点能量消耗的主要因素节点传输1比特的能量可执行3000条计算指令[1]由于多数传感器网络数据负荷通常为816比特[6]源地址与目的地址之和可能比数据负荷大使得MAC报文通信能量效率低减小传感器网络MAC地址长度对减小节点通信能量开销具有重要意义第18卷第7期Vol.
18No.
72006年7月蔡一兵等无线传感器网络低功耗混合地址编码算法July,20061931MAC地址在数据转发过程用于标识下一跳传感器节点节点收到数据包后检查本节点路由表确定下一跳MAC地址这个过程延续到数据包达到目的节点无线传感器网络一般采用无线多跳方式通信MAC地址具有空间复用特性只要保证节点MAC地址在传输邻居间唯一在传输邻居以外重复使用不影响MAC地址的邻居节点标识功能图1网络共有41个节点利用MAC地址空间复用特性只需7个MAC地址就可满足MAC地址分配需求每个节点周边标注数字为该节点的MAC地址编号不同MAC地址编号的节点通过不同几何图形进行区分由于只需要维护MAC地址在传输邻居间唯一性不用维护在全球或全网范围的唯一性因此可以有效缩短MAC地址长度减小通信能量开销具体的分布式MAC地址按需分配算法描述参见[5]图1MAC地址的空间复用示意图在分布式MAC地址按需分配算法中每个节点选用传输邻居间唯一的最小编号地址这将导致以下地址选择频率统计特性小编号地址的选择频率要大于大编号地址的选择频率如图2所示利用这个统计特性结合哈夫曼编码原理[7]对选择频率大的地址采用短地址编码对选择频率小的地址采用长地址编码可进一步缩短地址编码的平均长度00.
010.
020.
030.
040.
050.
060.
070.
0805101520253035AddressselectionfrequencyAddressAddressselectionfrequency图2地址选择频率统计曲线哈夫曼地址编码机制[5]如下首先根据预测网络部署密度和网络规模进行MAC地址分配网络仿真然后对仿真地址分配结果进行哈夫曼编码每个节点在网络部署前预先存储哈夫曼地址编码映射表网络部署后利用MAC地址按需分配算法选择传输邻居间唯一的地址节点发送MAC报文前对报文的源地址和目的地址用哈夫曼编码代替收到MAC报文后通过哈夫曼译码得到源地址和目的地址值得注意的是分布式MAC地址按需分配算法和哈夫曼地址编码都只涉及到MAC层的单播地址2地址编码要求分析地址编码要求分析地址编码要求分析地址编码要求分析任何网络的地址编码方案都需要考虑不同因素的影响否则难以实际使用本节从无线传感器网络MAC地址编码要求出发对哈夫曼地址编码和定长地址编码进行比较分析(1)地址编码的通信能量开销无线传感器网络是能量有限数据负荷小的分布式系统MAC报文是链路层以上各层报文的公共承载报文减小MAC地址的通信能量开销对于延长无线传感器网络寿命具有重要意义哈夫曼编码作为字符编码常用于数据文件压缩哈夫曼地址编码巧妙地将其应用到地址编码与定长地址编码相比哈夫曼地址编码缩短了地址编码平均长度减小了地址编码通信能量开销(2)地址编码容量MAC地址空间复用特性使得网络所需的地址总数与网路节点部署密度紧密相关一方面仿真依据的预测节点部署密度与实际部署密度可能存在差异另一方面随着网络节点总数增大某个节点选用非常大编号的地址k的可能性增加如果k>|A||A|为仿真得到地址总数将出现地址编码溢出选择地址k的节点将无法通信因此要求地址编码容量具有一定安全边界定长地址编码通过增加码长可以预留安全边界定长地址编码码长每增加1比特长地址编码将增加一倍效果明显哈夫曼地址编码的编码容量等于仿真地址总数没有安全边界保护地址编码容易溢出(3)广播地址问题无线传感器网络MAC地址类型通常包括单播地址和广播地址在多跳无线共享信道条件下使用广播报文可提高数据发布效率为此广播报文和广播地址被网络各层协议广泛应用如邻居发现协议[8]基于广播信道的SPINBC路由协议[9]基于定向扩散的路由协议[10]与单播地址相比广播地址被网络所有节点使用使用频率高通过增加码长定长地址编码可为不同地址类型预留编码空间哈夫曼地址编码根据单播地址的选择频率进行优化编码哈夫曼地址编码表不包括广播地址编码影响了网络协议的设计和已有协议的运行(4)地址编码公平性哈夫曼编码是变长二进制编码方法对编码长度不作任何限制选择频率低的地址对应编码长度可能是地址编码平均长度的好几倍使用这类地址编码的节点其地址通信能量开销将大于周围的节点极端情况下如果长地址编码1111111132222222222457733333344445555666667776111154第18卷第7期Vol.
18No.
72006年7月系统仿真学报July,20061932被流量大的节点选择使用节点的地址能量消耗更快节点使用寿命将小于其他节点因此从单节点角度看哈夫曼地址编码存在地址编码不公平现象定长地址编码的二进制编码码长都相同不存在地址编码公平性问题从上面分析可知地址编码容量和对不同地址类型的编码支持直接影响了地址编码实用性减小地址编码长度和平均长度反映了MAC地址编码的低功耗要求地址编码公平性的改善有助于降低使用长地址编码的节点的通信能量开销设计无线传感器网络低功耗MAC地址编码应该综合考虑以上因素的影响现有哈夫曼地址编码的平均长度小于定长地址编码但地址编码容量没有安全边界不支持广播地址编码存在地址分配公平性问题定长地址编码的平均长度大于哈夫曼地址编码但地址编码安全边界设置灵活可预留富余地址编码空间用于支持广播地址编码及防止地址溢出两种地址编码方法各有利弊3地址编码定性分析地址编码定性分析地址编码定性分析地址编码定性分析为了更严格分析地址编码对无线传感器网络地址通信能量开销地址编码容量地址编码公平性的影响提出以下编码性能参数3.
1编码性能参数定义编码性能参数定义编码性能参数定义编码性能参数定义设仿真地址表为A地址编码表为B地址i的选择频率为p(i)地址i的二进制编码长度为len(i)z地址编码平均长度地址编码平均长度地址编码平均长度地址编码平均长度∑=*=||1)()(AiilenipLen地址编码平均长度Len反映了地址编码的节能效果地址编码平均长度越短MAC地址通信能量开销越小z地址编码富余度地址编码富余度地址编码富余度地址编码富余度地址编码富余个数定义为||||ABM=地址编码富余度定义为|||)||(|'AABM=该指标反映了地址编码容量的安全边界富余地址编码可防止地址溢出并可用于支持广播地址编码z地址编码公平性地址编码公平性地址编码公平性地址编码公平性∑=*=||1)()(AiiipF其中25后线性逼近某个值该值为哈夫曼地址编码的地址编码平均长度加155.
566.
5705101520253035AddresscodeaveragelengthEncodingchangedaddressAddresscodeaveragelength图4地址编码平均长度调整曲线2对地址编码富余度影响从图5看到随着编码转换地址j增大富余地址编码个数M(j)曲线呈周期性锯齿变化与定长地址编码码长)(jα曲线在横轴方向变换趋势保持同步)(jα从7逐步减小到2M(j)极大值按照2的幂次逐步减小||2)(1)(AjjMj+=α3对地址编码公平性影响从图6中可以看到随着编码转换地址j增大地址编码公平性从最小值点开始逐步增大然后下滑到极小值点再逐步平滑上升最后逼近哈夫曼编码的地址编码公平性4最优编码转换地址结合图46可知选择不同的编码转换地址对混合地址编码的编码性能影响非常大原因在于调节编码转换地址相当于调节哈夫曼编码和定长编码比例在确定最优编码转换地址时主要考虑地址编码富余个数和地址编码平均长度指标并且优先考虑地址编码富余个数观察图4和5编码转换地址j17为最优编码转换地址EncodingchangedaddressMarginofAddresscode--M(j)Fixedsizecodelength—α(j)0510152025303505101520253035图5)(jα与)(jM的变化曲线00.
010.
020.
030.
040.
0505101520253035FairnessofAddresscodeEncodingchangedaddressFairnessofAddresscode--F(j)图6地址公平性的F(j)变化曲线4.
3三种编码算法性能比较三种编码算法性能比较三种编码算法性能比较三种编码算法性能比较表2为三种地址编码算法性能参数哈夫曼编码的地址编码富余个数为0安全边界太小不包括广播地址编码编码方案不可取定长编码和混合编码对应的地址编码容量分别为64和46地址编码富余个数分别为33和16满足节点邻居度为10的网络配置的地址编码容量安全边界要求但后者地址编码平均长度要小于前者因此混合编码要优于定长编码表表表表2三种地址编码算法性能三种地址编码算法性能三种地址编码算法性能三种地址编码算法性能哈夫曼地址编码混合地址编码定长地址编码地址编码平均长度4.
2705.
1806地址编码富余个数01631地址编码富余度00.
4890.
939地址编码公平性0.
0420.
0280混合地址编码和哈夫曼地址编码的二进制地址编码见表3定长地址编码的二进制编码略5结论结论结论结论无线传感器网络低功耗MAC地址编码设计需要综合考虑地址通信能量开销地址编码容量不同地址类型支持等因素的影响现有的定长地址编码和哈夫曼地址编码方法各有利弊本文提出的混合地址编码算法融合了两种地址编码优点较好地满足了无线传感器网络低功耗MAC地址编码的设计要求第18卷第7期Vol.
18No.
72006年7月系统仿真学报July,20061934表表表表3两种地址编码算法的二进制地址编码两种地址编码算法的二进制地址编码两种地址编码算法的二进制地址编码两种地址编码算法的二进制地址编码地址编号哈夫曼地址编码混合地址编码地址编号12345678910111213141516171819202122232425262728293031323311111110110110111010100110000110010101000011001000001100111000011100001001111100011100011001111000111101001111011001111011110111101110101111011100101111011100010111101110000101111011100000001111011100000100111101110000011001111011100000111101111011100000111001111011100110101011010100100101000001100010100100000110001000000011001011000001110000010100000100001100010100011100100100101100110100111101000101001101010101011101100101101101110101111110000.
.
.
11111112345678910111213141516171819202122232425262728293031323334.
.
.
49参考文献参考文献参考文献参考文献:[1]PottieGJ,KaiserWJ.
WirelessIntegratedNetworkSensors[J].
CommunicationoftheACM(S0001-0782),2000,43(5):51–58.
[2]ElsonJ.
RandomEphemeralTransactionIdentifiersinDynamicSensorNetworks[C]//ICDCS'01,Phoenix,AZ,2001.
[3]BolengJ.
EfficientNetworkLayerAddressingforMobileAdHocNetworks[C]//InProceedingsoftheInternationalConferenceonWirelessNetworks(ICWN'02).
LasVegas,NV,June2002[4]AliM,UzmiZA.
AnEnergy-EfficientNodeAddressNamingSchemeforWirelessSensorNetworks[C]//InNetworkingandCommunicationConferenceINCC'04.
Lahore,Pakistan:IEEEPressJune2004[5]SchurgersC.
DistributedOn-DemandAddressAssignmentinWirelessSensorNetworks[J].
IEEEParallelandDistributedSystems(S1045-9219),2002,13(10):1056–1065.
[6]SohrabiK,GaoJ,AilawadhiV,PottieG.
ProtocolsforSelf-OrganizationofaWirelessSensorNetwork[J].
IEEEPersonalComm.
Mag(S1070-9916),2000,7(5):16-27.
[7]CoverT,ThomasJ.
ElementsofInformationTheory[M].
Wiley,1991.
[8]GlynnMMc,BorbashS.
BirthdayProtocolsforLowEnergyDeploymentandFlexibleNeighborDiscoveryinAdHocWirelessNetworks[C]//Proc.
Conf.
MobiHoc2001.
LongBeach,CA,USA:ACMPress2001:137-145[9]KulikJ,HeinzelmanWR,BalakrishnanH.
Negotiation-basedProtocolsforDisseminatingInformationinWirelessSensorNetworks[J].
WirelessNetworks(S1022-0038),2002,8:169-185.
[10]IntanagonwiwatC,GovindanR,EstrinD,HeidemannJ,SilvaF.
DirectedDiffusionforWirelessSensorNetworking.
Networking[J].
IEEE/ACMTransactionsonNetworking(S1063-6692),2003,11(1):2–16.
上接第1929页[2]NJBelkin,DKelly,G.
Kim,J-YKim,H-JLee,G.
Muresan,M-CTang,X-JYuan,CCool.
Querylengthininteractiveinformationretrieval[C]//Proceedingsofthe26thannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval.
NewYork:ACMPress,2003:205-212.
[3]HideoJoho,ClaireCoverson,MarkSanderson,MichelineBeaulieu.
Hierarchicalpresentationofexpansionterms[C]//Proceedingsofthe2002ACMsymposiumonAppliedcomputing.
NewYork:ACMPress,2002:645-649.
[4]XuehuaShen,ChengXiangZhai.
Exploitingqueryhistoryfordocumentrankingininteractiveinformationretrieval[C]//Proceedingsofthe26thannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval.
NewYork:ACMPress,2003:377-378.
[5]CarolynJ.
Crouch,DonaldB.
Crouch,QingyanChen,StevenJ.
Holtz.
Improvingtheretrievaleffectivenessofveryshortqueries[J].
InformationProcessingandManagement(S0306-4573),2002,38(1):1-36.
[6]MShamimKhan,SebastianKhor.
Enhancedwebdocumentretrievalusingautomaticqueryexpansion[J].
JournaloftheAmericanSocietyforInformationScienceandTechnology(S1532-2882),2004,55(1):29-40.
[7]KidukYang.
Combiningtext-,link-,andclassification-basedretrievalmethodstoenhanceinformationdiscoveryontheWeb[D].
PHDthesis,ChapelHill:Univ.
ofNorthCarolina,2002-5,157-171.
[8]MingFangWu,MichaelFuller,RossWilkinson.
UsingClusteringandClassificationApproachesinInteractiveRetrieval[J].
InformationProcessing&Management(S0306-4573),2001,37(3):459-484.
[9]AntonLeuski.
EvaluatingDocumentClusteringforInteractiveInformationRetrieval[C]//IntheProceedingsoftheACMCIKM2001TenthInternationalConferenceonInformationandKnowledgeManagement.
NewYork:ACMPress,2001:33-40.
[10]LeuskiJAllan.
Improvinginteractiveretrievalbycombiningrankedlistsandclustering[C]//IntheproceedingsofRIAO2000conference.
Paris,2000:665-681.
[11]Salton,GWong,AandYang,C.
S.
Onthespecificationoftermvaluesinautomaticindexing[J].
JournalofDocumentation,1973,29(4):351-372.
[12]RicardoB-Y,BerthierR-N.
ModernInformationRetrieval[M].
England:PearsonEducationLimited,1999.
[13]韩立新,陈贵海,谢立.
一个面向Internet的个性化信息检索系统模型[J].
电子学报,2002,30(2):240-244.
[14]ZhongMinjuan,ChenZhiping,LinYaping.
Usingclassificationandkeyphraseextractionforinformationretrieval[C]//ProceedingsoftheWorldCongressonIntelligentControlandAutomation.
HangZhou:IEEEComputerSocietyPress,2004:3037-3041.