年7 月系统仿真学报.pdf

上传人:qwe****56 文档编号:74654632 上传时间:2023-02-27 格式:PDF 页数:5 大小:466.87KB
返回 下载 相关 举报
年7 月系统仿真学报.pdf_第1页
第1页 / 共5页
年7 月系统仿真学报.pdf_第2页
第2页 / 共5页
点击查看更多>>
资源描述

《年7 月系统仿真学报.pdf》由会员分享,可在线阅读,更多相关《年7 月系统仿真学报.pdf(5页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 18 卷第 7期 系系系系 统统统统 仿仿仿仿 真真真真 学学学学 报报报报 Vol.18 No.7 2006 年 7 月 Journal of System Simulation July,2006 1930 无线传感器网络低功耗混合地址编码算法无线传感器网络低功耗混合地址编码算法无线传感器网络低功耗混合地址编码算法无线传感器网络低功耗混合地址编码算法 蔡一兵1,2李海波1王春峰1陈 沫1李忠诚1 1.中国科学院计算技术研究所信息网络室北京 1000802.中国科学院研究生院北京 100080 摘摘摘摘 要要要要无线传感器网络低功耗 MAC 地址编码设计需要综合考虑地址通信能量开销地址编

2、码容量 不同地址类型支持等因素的影响 首先分析了现有定长地址编码和哈夫曼地址编码算法的优缺点给出了地址编码性能评估参数给出了地址编码性能评估参数给出了地址编码性能评估参数给出了地址编码性能评估参数接着提出了一种混合地址编码算法接着提出了一种混合地址编码算法接着提出了一种混合地址编码算法接着提出了一种混合地址编码算法仿真结果表明新算法融合了两种地址编码优点较好地满足了无线传感器网络低功耗 MAC 地址编码的设计要求 关键词关键词关键词关键词无线传感器网络低功耗地址哈夫曼编码 中图分类号中图分类号中图分类号中图分类号TP393.04 文献标识码文献标识码文献标识码文献标识码A 文章编号文章编号文章

3、编号文章编号1004-731X(2006)07-1930-05 Method of Low Power Mixing Address Coding in Wireless Sensor Networks CAI Yi-bing1,2,LI Hai-bo1,WANG Chun-feng1,CHEN Mo1,LI Zhong-cheng1(1.Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100080,China 2.Graduate School of the Chinese Academy of Sc

4、iences,Chinese Academy of Sciences,Beijing 100080,China Abstract:The design of low power MAC address coding in wireless sensor networks must consider the effect of following factors,such as the energy consumption of address transmission,the capacity of address codes and the support of different addr

5、ess types.The advantages and disadvantages of current methods of fixed size coding and Huffman address coding are analyzed.A mixing address coding is presented and the performance parameters of address coding are put forward.The simulation results show that the new method merges the advantages of tw

6、o kinds of address coding method and satisfies the design requirements of low power MAC address coding in wireless sensor networks.Key words:wireless sensor networks;low power;address;Huffman coding 引引引引 言言言言1 无线传感器网络是由众多微小传感器节点通过无线多跳自组织方式构成的网络可实现物理世界计算世界以及人类社会的相互连通 能量问题是传感器网络的核心问题之一1近几年来研究人员开始关注传感器

7、网络低功耗地址机制研究如何减小地址长度以降低地址通信能量开销2-5文5利用无线多跳共享信道下 MACMedium Access Control地址空间复用特性提出分布式 MAC 地址按需分配算法和哈夫曼地址编码方法减小了地址编码长度有效降低了地址通信能量开销 地址机制是信息网络设计的最基本问题 一个实用的地址机制应综合考虑各种因素影响 无线传感器网络节点能量有限 减小地址编码长度及平均长度对延长节点及网络寿命非常重要这是无线传感器网络与其他网络的显著区别此外地址编码容量是否富余编码是否支持不同地址类型同样也不容忽略 传统的定长地址编码在地址编码容量富余设 收稿日期收稿日期收稿日期收稿日期200

8、5-06-02 修回日期修回日期修回日期修回日期2005-08-03 基金项目基金项目基金项目基金项目国家自然科学基金60273021,中科院计算所青年创新基金2005660012 作者简介作者简介作者简介作者简介蔡一兵蔡一兵蔡一兵蔡一兵1971男福建长汀人工程师博士生研究方向为无线自组织网络李海波李海波李海波李海波1984男河南周口市人硕博连读生研究方向为无线自组织网络王春峰王春峰王春峰王春峰1976男山东淄博人助研博士研究方向为 QOS 控制陈沫陈沫陈沫陈沫1981男江苏盐城人硕博连读生研究方向为无线自组织网络李忠诚李忠诚李忠诚李忠诚1961-男黑龙江哈尔滨人研究员博导研究方向为下一代网络

9、 计不同地址类型编码支持方面要比哈夫曼地址编码灵活哈夫曼地址编码的平均长度要小于定长地址编码 但未考虑后面的因素影响了哈夫曼地址编码的实际应用 本文首先介绍了无线传感器网络MAC地址编码的相关研究然后从无线传感器网络低功耗 MAC 地址编码要求出发 对哈夫曼地址编码和定长地址编码的利弊进行了详细分析接着提出了一种低功耗混合地址编码算法给出了地址编码性能评估参数 在此基础上对各种地址编码算法进行仿真性能比较仿真结果表明新算法融合了两种地址编码优点较好满足了无线传感器网络 MAC 地址编码要求 1 地址编码相关研究地址编码相关研究地址编码相关研究地址编码相关研究 现有地址编码包括定长地址编码和哈夫

10、曼地址编码 为了方便目前传感器网络采用定长地址编码机制 给节点静态配置在全球或全网范围内唯一的 MAC 地址地址编码长度由预计节点总数确定所有地址编码长度相同 无线传感器节点电源能量极其有限 很多情况下传感器节点数目众多并分散在条件恶劣的远程环境电池更换困难能量耗尽是传感器节点失效的主要原因通信能量开销是节点能量消耗的主要因素 节点传输 1 比特的能量可执行3 000 条计算指令1由于多数传感器网络数据负荷通常为 816 比特6源地址与目的地址之和可能比数据负荷大使得 MAC 报文通信能量效率低减小传感器网络 MAC 地址长度对减小节点通信能量开销具有重要意义 第 18 卷第 7 期 Vol.

11、18 No.7 2006年7月 蔡一兵 等 无线传感器网络低功耗混合地址编码算法 July,2006 1931 MAC 地址在数据转发过程用于标识下一跳传感器节点节点收到数据包后检查本节点路由表确定下一跳 MAC 地址这个过程延续到数据包达到目的节点无线传感器网络一般采用无线多跳方式通信MAC 地址具有空间复用特性只要保证节点 MAC 地址在传输邻居间唯一在传输邻居以外重复使用不影响 MAC 地址的邻居节点标识功能图 1 网络共有 41 个节点利用 MAC 地址空间复用特性只需 7 个MAC 地址就可满足 MAC 地址分配需求每个节点周边标注数字为该节点的 MAC 地址编号 不同 MAC 地址

12、编号的节点通过不同几何图形进行区分由于只需要维护 MAC 地址在传输邻居间唯一性不用维护在全球或全网范围的唯一性因此可以有效缩短 MAC 地址长度减小通信能量开销具体的分布式 MAC 地址按需分配算法描述参见5 图 1 MAC 地址的空间复用示意图 在分布式 MAC 地址按需分配算法中每个节点选用传输邻居间唯一的最小编号地址这将导致以下地址选择频率统计特性小编号地址的选择频率要大于大编号地址的选择频率如图 2 所示利用这个统计特性结合哈夫曼编码原理7对选择频率大的地址采用短地址编码对选择频率小的地址采用长地址编码 可进一步缩短地址编码的平均长度 0 0.01 0.02 0.03 0.04 0.

13、05 0.06 0.07 0.08 0 5 10 15 20 25 30 35Address selection frequency Address Address selection frequency 图 2 地址选择频率统计曲线 哈夫曼地址编码机制5如下首先根据预测网络部署密度和网络规模进行 MAC 地址分配网络仿真然后对仿真地址分配结果进行哈夫曼编码 每个节点在网络部署前预先存储哈夫曼地址编码映射表网络部署后利用 MAC 地址按需分配算法选择传输邻居间唯一的地址节点发送 MAC 报文前对报文的源地址和目的地址用哈夫曼编码代替收到MAC 报文后通过哈夫曼译码得到源地址和目的地址值得注意的

14、是分布式 MAC 地址按需分配算法和哈夫曼地址编码都只涉及到 MAC 层的单播地址 2 地址编码要求分析地址编码要求分析地址编码要求分析地址编码要求分析 任何网络的地址编码方案都需要考虑不同因素的影响否则难以实际使用本节从无线传感器网络 MAC 地址编码要求出发 对哈夫曼地址编码和定长地址编码进行比较分析 (1)地址编码的通信能量开销 无线传感器网络是能量有限数据负荷小的分布式系统MAC 报文是链路层以上各层报文的公共承载报文减小MAC 地址的通信能量开销对于延长无线传感器网络寿命具有重要意义 哈夫曼编码作为字符编码常用于数据文件压缩哈夫曼地址编码巧妙地将其应用到地址编码与定长地址编码相比哈夫

15、曼地址编码缩短了地址编码平均长度减小了地址编码通信能量开销(2)地址编码容量 MAC 地址空间复用特性使得网络所需的地址总数与网路节点部署密度紧密相关 一方面仿真依据的预测节点部署密度与实际部署密度可能存在差异 另一方面随着网络节点总数增大某个节点选用非常大编号的地址 k 的可能性增加如果 k|A|A|为仿真得到地址总数将出现地址编码溢出选择地址 k 的节点将无法通信因此要求地址编码容量具有一定安全边界 定长地址编码通过增加码长可以预留安全边界 定长地址编码码长每增加 1 比特长地址编码将增加一倍效果明显哈夫曼地址编码的编码容量等于仿真地址总数没有安全边界保护地址编码容易溢出(3)广播地址问题

16、 无线传感器网络MAC 地址类型通常包括单播地址和广播地址 在多跳无线共享信道条件下使用广播报文可提高数据发布效率 为此广播报文和广播地址被网络各层协议广泛应用如邻居发现协议8基于广播信道的 SPINBC 路由协议9基于定向扩散的路由协议10与单播地址相比广播地址被网络所有节点使用使用频率高 通过增加码长 定长地址编码可为不同地址类型预留编码空间 哈夫曼地址编码根据单播地址的选择频率进行优化编码哈夫曼地址编码表不包括广播地址编码影响了网络协议的设计和已有协议的运行(4)地址编码公平性 哈夫曼编码是变长二进制编码方法 对编码长度不作任何限制选择频率低的地址对应编码长度可能是地址编码平均长度的好几

17、倍使用这类地址编码的节点其地址通信能量开销将大于周围的节点极端情况下如果长地址编码 1 1 1 1 1 1 1 1 3 2 2 2 2 2 2 2 2 2 2 4 5 7 7 3 3 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 6 7 7 7 6 1 1 1 1 5 4 第 18 卷第 7 期 Vol.18 No.7 2006 年 7 月 系 统 仿 真 学 报 July,2006 1932 被流量大的节点选择使用节点的地址能量消耗更快节点使用寿命将小于其他节点因此从单节点角度看哈夫曼地址编码存在地址编码不公平现象 定长地址编码的二进制编码码长都相同不存在地址编码公平性问题

18、 从上面分析可知地址编码容量和对不同地址类型的编码支持直接影响了地址编码实用性减小地址编码长度和平均长度反映了 MAC 地址编码的低功耗要求地址编码公平性的改善有助于降低使用长地址编码的节点的通信能量开销设计无线传感器网络低功耗 MAC 地址编码应该综合考虑以上因素的影响 现有哈夫曼地址编码的平均长度小于定长地址编码 但地址编码容量没有安全边界不支持广播地址编码存在地址分配公平性问题 定长地址编码的平均长度大于哈夫曼地址编码但地址编码安全边界设置灵活可预留富余地址编码空间用于支持广播地址编码及防止地址溢出两种地址编码方法各有利弊 3 地址编码定性分析地址编码定性分析地址编码定性分析地址编码定性

19、分析 为了更严格分析地址编码对无线传感器网络地址通信能量开销地址编码容量地址编码公平性的影响提出以下编码性能参数 3.1 编码性能参数定义编码性能参数定义编码性能参数定义编码性能参数定义 设仿真地址表为 A地址编码表为 B地址 i 的选择频率为 p(i)地址 i 的二进制编码长度为 len(i)?地址编码平均长度地址编码平均长度地址编码平均长度地址编码平均长度=|1)()(AiilenipLen 地址编码平均长度Len反映了地址编码的节能效果地址编码平均长度越短 MAC 地址通信能量开销越小?地址编码富余度地址编码富余度地址编码富余度地址编码富余度 地址编码富余个数定义为|ABM=地址编码富余

20、度定义为|)|(|AABM=该指标反映了地址编码容量的安全边界 富余地址编码可防止地址溢出并可用于支持广播地址编码?地址编码公平性地址编码公平性地址编码公平性地址编码公平性=|1)()(AiiipF其中 25 后线性逼近某个值该值为哈夫曼地址编码的地址编码平均长度加 1 5 5.5 6 6.5 7 0 5 10 15 20 25 30 35 Address code average lengthEncoding changed address Address code average length 图 4 地址编码平均长度调整曲线 2对地址编码富余度影响 从图 5 看到随着编码转换地址 j 增

21、大富余地址编码个数 M(j)曲线呈周期性锯齿变化 与定长地址编码码长)(j曲线在横轴方向变换趋势保持同步)(j从 7 逐步减小到 2M(j)极大值按照 2 的幂次逐步减小|2)(1)(AjjMj+=3对地址编码公平性影响 从图 6 中可以看到随着编码转换地址 j 增大地址编码公平性从最小值点开始逐步增大然后下滑到极小值点再逐步平滑上升最后逼近哈夫曼编码的地址编码公平性 4最优编码转换地址 结合图 46 可知选择不同的编码转换地址对混合地址编码的编码性能影响非常大 原因在于调节编码转换地址相当于调节哈夫曼编码和定长编码比例 在确定最优编码转换地址时 主要考虑地址编码富余个数和地址编码平均长度指标

22、并且优先考虑地址编码富余个数观察图 4 和 5编码转换地址 j17 为最优编码转换地址 Encoding changed address Margin of Address code-M(j)Fixed size code length(j)0 5 10 15 20 25 30 35 0 5 10 15 20 25 30 35 图 5 )(j与)(jM的变化曲线 0 0.01 0.02 0.03 0.04 0.05 0 5 10 15 20 25 30 35 Fairness of Address code Encoding changed address Fairness of Addres

23、s code-F(j)图 6 地址公平性的F(j)变化曲线 4.3 三种编码算法性能比较三种编码算法性能比较三种编码算法性能比较三种编码算法性能比较 表 2 为三种地址编码算法性能参数 哈夫曼编码的地址编码富余个数为 0安全边界太小不包括广播地址编码编码方案不可取 定长编码和混合编码对应的地址编码容量分别为 64 和 46地址编码富余个数分别为 33 和 16满足节点邻居度为 10 的网络配置的地址编码容量安全边界要求但后者地址编码平均长度要小于前者因此混合编码要优于定长编码 表表表表 2 三种地址编码算法性能三种地址编码算法性能三种地址编码算法性能三种地址编码算法性能 哈夫曼 地址编码 混合

24、 地址编码 定长 地址编码 地址编码平均长度 4.270 5.180 6 地址编码富余个数 0 16 31 地址编码富余度 0 0.489 0.939 地址编码公平性 0.042 0.028 0 混合地址编码和哈夫曼地址编码的二进制地址编码见表 3定长地址编码的二进制编码略 5 结论结论结论结论 无线传感器网络低功耗 MAC 地址编码设计需要综合考虑地址通信能量开销地址编码容量不同地址类型支持等因素的影响 现有的定长地址编码和哈夫曼地址编码方法各有利弊 本文提出的混合地址编码算法融合了两种地址编码优点较好地满足了无线传感器网络低功耗 MAC 地址编码的设计要求 第 18 卷第 7 期 Vol.

25、18 No.7 2006 年 7 月 系 统 仿 真 学 报 July,2006 1934 表表表表 3 两种地址编码算法的二进制地址编码两种地址编码算法的二进制地址编码两种地址编码算法的二进制地址编码两种地址编码算法的二进制地址编码 地址编号 哈夫曼地址编码 混合地址编码 地址编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 1111 1110 1101 1011 1010 1001 1000 0110 0101 0100 0011 0010 0000 11

26、001 11000 01110 00010 011111 000111 000110 0111100 01111010 011110110 0111101111 01111011101 011110111001 0111101110001 01111011100001 011110111000000 0111101110000010 01111011100000110 011110111000001111 011110111000001110 01111 01110 01101 01011 01010 01001 01000 00110 00101 00100 00011 00010 0000

27、0 011001 011000 001110 000010 100000 100001 100010 100011 100100 100101 100110 100111 101000 101001 101010 101011 101100 101101 101110 101111 110000.111111 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34.49 参考文献参考文献参考文献参考文献:1 Pottie G J,Kaiser W J.Wireles

28、s Integrated Network SensorsJ.Communication of the ACM(S0001-0782),2000,43(5):5158.2 Elson J.Random Ephemeral Transaction Identifiers in Dynamic Sensor NetworksC/ICDCS01,Phoenix,AZ,2001.3 Boleng J.Efficient Network Layer Addressing for Mobile Ad Hoc NetworksC/In Proceedings of the International Conf

29、erence on Wireless Networks(ICWN02).Las Vegas,NV,June 2002 4 Ali M,Uzmi Z A.An Energy-Efficient Node Address Naming Scheme for Wireless Sensor NetworksC/In Networking and Communication ConferenceINCC04.Lahore,Pakistan:IEEE Press June 2004 5 Schurgers C.Distributed On-Demand Address Assignment in Wir

30、eless Sensor NetworksJ.IEEE Parallel and Distributed Systems(S1045-9219),2002,13(10):1056 1065.6 Sohrabi K,Gao J,Ailawadhi V,Pottie G.Protocols for Self-Organization of a Wireless Sensor NetworkJ.IEEE Personal Comm.Mag(S1070-9916),2000,7(5):16-27.7 Cover T,Thomas J.Elements of Information TheoryM.Wi

31、ley,1991.8 Glynn M Mc,Borbash S.Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless NetworksC/Proc.Conf.MobiHoc 2001.Long Beach,CA,USA:ACM Press2001:137-145 9 Kulik J,Heinzelman W R,Balakrishnan H.Negotiation-based Protocols for Disseminating Information i

32、n Wireless Sensor NetworksJ.Wireless Networks(S1022-0038),2002,8:169-185.10 Intanagonwiwat C,Govindan R,Estrin D,Heidemann J,Silva F.Directed Diffusion for Wireless Sensor Networking.NetworkingJ.IEEE/ACM Transactions on Networking(S1063-6692),2003,11(1):2 16.上接第 1929 页 2 N J Belkin,D Kelly,G.Kim,J-Y

33、 Kim,H-J Lee,G.Muresan,M-C Tang,X-J Yuan,C Cool.Query length in interactive information retrieval C/Proceedings of the 26th annual international ACM SIGIR conference on Research and development in information retrieval.New York:ACM Press,2003:205-212.3 Hideo Joho,Claire Coverson,Mark Sanderson,Miche

34、line Beaulieu.Hierarchical presentation of expansion termsC/Proceedings of the 2002 ACM symposium on Applied computing.New York:ACM Press,2002:645-649.4 Xuehua Shen,Cheng Xiang Zhai.Exploiting query history for document ranking in interactive information retrievalC/Proceedings of the 26th annual int

35、ernational ACM SIGIR conference on Research and development in information retrieval.New York:ACM Press,2003:377-378.5 Carolyn J.Crouch,Donald B.Crouch,Qingyan Chen,Steven J.Holtz.Improving the retrieval effectiveness of very short queries J.Information Processing and Management(S0306-4573),2002,38(

36、1):1-36.6 M Shamim Khan,Sebastian Khor.Enhanced web document retrieval using automatic query expansion J.Journal of the American Society for Information Science and Technology(S1532-2882),2004,55(1):29-40.7 Kiduk Yang.Combining text-,link-,and classification-based retrieval methods to enhance inform

37、ation discovery on the WebD.PHD thesis,Chapel Hill:Univ.of North Carolina,2002-5,157-171.8 MingFang Wu,Michael Fuller,Ross Wilkinson.Using Clustering and Classification Approaches in Interactive Retrieval J.Information Processing&Management(S0306-4573),2001,37(3):459-484.9 Anton Leuski.Evaluating Do

38、cument Clustering for Interactive Information Retrieval C/In the Proceedings of the ACM CIKM 2001 Tenth International Conference on Information and Knowledge Management.New York:ACM Press,2001:33-40.10 Leuski J Allan.Improving interactive retrieval by combining ranked lists and clusteringC/In the pr

39、oceedings of RIAO 2000 conference.Paris,2000:665-681.11 Salton,G Wong,A and Yang,C.S.On the specification of term values in automatic indexing J.Journal of Documentation,1973,29(4):351-372.12 Ricardo B-Y,Berthier R-N.Modern Information RetrievalM.England:Pearson Education Limited,1999.13 韩立新,陈贵海,谢立.一个面向 Internet 的个性化信息检索系统模型J.电子学报,2002,30(2):240-244.14 Zhong Minjuan,Chen Zhiping,Lin Yaping.Using classification and key phrase extraction for information retrievalC/Proceedings of the World Congress on Intelligent Control and Automation.HangZhou:IEEE Computer Society Press,2004:3037-3041.

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 技术资料 > 其他杂项

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁