基于小世界的无线传感器网络资源查询机制
文章编号：１６７１—４５９８（２００６）１２—１７５６一０３
中图分类号：ＴＰ３９３．０２文献标识码：Ａ
基于小世界的无线传感器网络资源查询机制
刘志强，蒋泽军，王丽芳，王．ｉｊ言吉，王高祖，姜
华
（西北工业大学，陕西西安
７１００７２）
摘要：多数无线传感器网络资源查询和路由协议都试图寻找源节点到目标节点的最优（短）路径，而针对于单次查询的数据传输量很小的情况，这些协议的效率是非常低的，因为大量的能量被消耗在建立最优（短）路径上，ｓＭＱＭ查询机制将着重于寻找一条“可行”的路径，而非“最优”路径，大大节省了路径查找的开销，从而降低了总的查询能耗；小世界理论表明在规则网络中，随机的加入少量的长程连接（ｓｈｏｒｔｃｕｔｓ），将大大的降低网络的直径，ｓＭＱＭ查询机制是在该理论和ｃＡＲＤ协议的基础上提出来的，它适用于大规模、高查询率而单次查询的数据传输量很小的无线传感器网络，ｓＭＱＭ性能的仿真试验结论说明，ｓＭＱＭ查询机制的性能优于ｃＡＲＤ协议。
关键词：小世界；长程连接；无线传感器网络；资源查询
Ｓｍａｌｌ—Ｗｏｒｌｄ
ＢａｓｅｄＡｒｃｈｉｔｅｃｔｕｒｅｆｏｒＲｅｓｏｕｒｃｅＤｉｓｃＯＶｅｒｙｉｎ
Ｗｉｒｅｌｅｓｓ
ＳｅｎｓｏｒＮｅｔｗＯｒｋｓ
ＬｉｕＺｈｉｑｉａｎｇ，Ｊｉａｎｇ
Ｚｅｊｕｎ，ＷａｎｇＬｉｆａｎｇ，ＷａｎｇＪｕｎｊｉ，ＷａｎｇＧａｏＺｕ，Ｊｉａｎｇ
Ｈｕａ
（ＮｏｒｔｈｗｅｓｔｅｒｎＰｏｌｖｔｅｃｈｎｉｃａｌＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ
７１００７２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：ｔｈｅｍａｊｏ“ｔｙｏｆｐｒｏｔｏｃｏｌｓｆｏｒ
ｒｏｕｔｉｎｇｉｎ
ｗｉｒｅｌｅｓｓ
ｓｅｎｓｏｒ
ｎｅｔｗｏｒｋｓａｔｔｅｍｐｔ
ｔｏ
ｏｂｔａｉｎｏｐｔｉｍａｌ
ｏｒ
ｓｈｏｒｔｅｓｔｐ８ｔｈｓ．Ｆｏｒｓｈｏｒｔ—ｌｉｖｅｄ
ａｎｄｓｍａｎｔｒａｎｓｆｅｆｓｃｏｎｎｅｃｔｉｏｎｓ，ｈｏｗｅｖｅｒ，ｔｈｏｓｅａｐｐｒｏａｃｈｅｓｍａｙｂｅ
ｑｕｉｔｅ
ｉｎｅｆｆｌｃｉｅｎｔ．Ｓｍａｌｌ—ｗｏｒｌｄｔｈｅｏｒｙ
ｐｒｅｓｅｎｔ
ｔｈａｔ
ａｖｅｒａｇｅｐａｔｈ１ｅｎｇｔｈ
ｃａｎ
ｂｅｇｒｅａｔｌｙｄｅｃｒｅａｓｅｄｂｙａｄｄ
ａ
ｆｅｗｏｆｌ。ｎｇ—ｒａｎｇｌｉｎｋｒａｎｄｏｍｌｙ
ｔｏ
ｒｅｇｕｌａｒｎｅｔｗｏｒｋｓ．ＳＭＱＭ
ｉｓ
ｏｎ
ｔｈｅｂａｓｉｓｏｆｐｒｏｄｕｃｔｉｏｎｏｆ
Ｓｍａｌｌ一Ｗｏｒｌｄ
ｔｈｅｏｒｙａｎｄＣＡＲＤｐｒｏｔｏｃｏｌ＿Ｔｈｅｍａｉｎｄｅｓ逸ｎｇｏａｌｉｎｓｕｃｈ
ｔａｒｇｅｔ
ａｐｐｌｉｃａｔｉｏｎｓ
ｉｓ
ｔｏ
ｒｅｄｕｃｅｃｏｍｍｕｎｉｃａｔｉｏｎｏｖｅｒｈｅａｄａｎｄ
ｐｏｗｅｒ
ｃｏｎｓｕｍｐｔｉｏｎ，
ｒａｔｈｅｒｔｈａｎ
ｒｏｕｔｅ
ｏｐｔｉｍｉｚａｔｉｏｎ．ＳｉｍｕｌａｔｉｏｎｓｓｈｏｗｔｈａｔＳＭＱＭｏｖｅｒｃｏｍｅｓＣＡＲＤｐｒｏｔｏｃ０１．
Ｋｅｙ
ｗｏｒｄ８：Ｓｍａｌｌ—ｗｏｒｌｄ；Ｃｏｎｔａｃｔ；Ｗｉｒｅｌｅｓｓ
ｓｅｎｓｏｒ
ｎｅｔｗｏｒｋｓ；ｒｅｓｏｕｒｃｅ
ｑｕｅｒｙ
０引言
１
基于Ｃｏｎｔａｃｔ的资源查询机制
无线传感器网络节点能量有限且难以补充，大量节点的失效将使网络失效。节点的存储能力和计算能力都不强，且无任何底层基础架构支持，因而无法实现集中控制。无线传感器网络的上述特点，使得资源查询成为非常具有挑战性问题。
本文介绍了一种基于Ｃｏｎｔａｃｔ的无线传感器网络资源查询机制一～ＳＭＱＭ。Ｃｏｎｔａｃｔ是由南加州大学的Ａｈｍｅｄ
ＨｅＩｍｙ
教授在２００２年提出来的概念口］。他根据小世界理论［２１］，提出Ａｄ—ｈｏｃ网络的各个节不仅维护它的”邻居”节点的资源状态，而且还选择维护少数较远节点的资源状态，这些较远的节点叫做ｃｏｎｔａｃｔ［“。Ｃｏｎｔａｃｔ就是网络中的长程连接（Ｓｈｏｒｔ—ｃｕｔｓ），它使得网络成为一个“小世界”，大大降低了查询源与目标的“分离度”。本文，基于ＣＡＲＤ协议的已有研究成果，将Ｃｏｎｔａｃｔ的概念引入无线传感器网络，提出了ＳＭＱＭ查询机制，ｓＭＱＭ重点改进了ＣＡＲＤＬ４＿５１协议的Ｃｏｎｔａｃｔ选择方法，通过仿真分析了该查询机制的性能和适用范围。
◆ｉ收稿日期：２００６一０９一１３；修回日期：２００６一１１一０３。
基金项目：陕西省自然科学基金项目（２００４Ａ０６）；陕西省自然科学基金项目（２００６Ｆ０８）。
作者简介：刘志强（１９７５一），男，内蒙古赤峰市人，博士生，主要从事１．１
相关定义
一≯
图１
基于Ｃｏｎｔａｃｔ的查询机制概览
无线传感器网络、复杂网络理论、网络安全方向的研究。
在本文中的相关定义我们基本沿用文献［４］中的相关定蒋泽军（１９６４一），男，硕士，教授，主要从事无线传感器网络、数据库义，如图１所示：
系统、嵌人式计算、网络安全等方向的研究。
１）（节点的）邻居：位于该节点周围Ｒ跳以内的所有节
中华测控网
ｃｈｉｎａｍｃａ．ｃ‘）１１１
万
方数据
黧蒸兰三兰罴；◆ｉ
３）ｃｏｎｔａｃｔ最大距离ｒ：ｃｏｎｔａｃｔ距离源节点的最大限制跳数，为了避免重叠，令ｒ≥２Ｒ；的最大数量；
４）最大ｃｏｎｔａｃｔ数量Ｎｏｃ：每个源节点可以选择ｃｏｎｔａｃｔ５）最大搜索深度Ｄ：源节点查询ｃｏｎｔａｃｔ的最大级数
＼／∥。．了／、√。口＼ｏ＼ｏ
Ｉ＼ｏ
．】煅？。弋、＼２，∥Ｙ／ｏｄ
。～Ｖ吃。，ｏ『．１瓢Ｘ
ｏ＼ｏ滚稻ｓ尹９，
刊ｏ、忒．“彩开蚓！∥．
。
ｏ。
＼、逸掰叫：。、
、、、√毽
等端徽要置ｉ！嚣？端嚣
Ｐ一缫
㈣
中华测控网
ｃ１１ｉ１１ｉＩｌｌｌｏ：ｌ“１ｎ１
万方数据
Ｌ
４器源节点ｓ需要查询一个目的节点或者目标源Ｔ喜６。。。厂＿＝Ｉ二—ｒ－————ｒ————ｒ—］
当某个任意源节点ｓ需要查询一个目的节点或者目标源Ｔ
：！！！！：盐蔓垫型量量鳖趔笙！！鲞
善。
如０Ｏ；ｌ
２
ＳＭＱＭ仿真分析
ｉ墨垂薹垂垂
中华测控网
ｃ１１ｉ１１“１１１ｃ：Ｉ．ｃ‘１１１１
万
方数据们０Ｏ如０Ｏ
∞ＯＯ
ｍＯ０
Ｏ
芒。｝Ｎ０ｄｅ
ｎ岫ｂｅｒｓ
０ｆｎｅｔｗｏ】ｒｋｓ
图４不同规模的网络中ＳＭＱＭ和ＣＡＲＤ单次查询的平均能耗比较
传感器网络中。
在其他的独立于地理位置信息、不需要集中控制的无线传感器网络查询机制中，Ｆｌｏｏｄｉｎｇ是最普遍的方法。Ｆｌｏｏｄｉｎｇ可以发现查询源到目标节点的最短（优）路径，而带来的最大的问题就是大量的路径发现能耗。如果每次查询目标需要传输的数据量很小（例如仅只是一个温度值），但是查询的频率却非常高时，这时最短（优）路径建立时大量的能耗和实际的小数
据量的传输能耗相比，最短（优）路径的建立变得得不偿失。基于Ｃｏｎｔａｃｔ的无线传感器网络资源查询机制每次查询得到的路径不是最短（优）的，但是，总查询能耗却非常的低，总体效果来看，将大大的降低无线传感器网络的查询能耗。
参考文献：［１］
ＨｅｌｍｙＡ，Ａｒｃｈｉｔｅｃｔｕｒａｌｆｒａｍｅｗｏｒｋｆｏｒｌａｒｇｅ—ｓｃａｌｅｍｕｌｔｉｃａｓｔ
ｉｎ
ｍｏｂｉｌｅａｄｈｏｃ
ｎｅｔｗｏｒｋｓ［Ａ］．ＩＥＥＥＩｎｔｅｒｎａｔ．ｃｏｎｆ．ｏｎｃｏｍｍｕｎｉ—
ｃａｔｉｏｎｓ（Ｉｃｃ）［ｃ］．ＮｅｗＹｏｒｋ，２００２，２０３６—２０４２．［２］ｗａｔｔｓＤ，ＳｔｒｏｇａｔｚＳ．
ｃｏｌｌｅｃｔｉｖｅ
ｄｙｎａｍｉｃｓｏｆ’ｓｍａｌｌ—ｗｏｒｌｄ
ｎｅｔ—
ｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ，１９９８，３９３：４４０一４４２．［３］ＫｌｅｉｎｂｅｒｇＪ．Ｎａｖｉｇａｔｉｎｇｉｎ
ａ
ｓｍａｕｗｏｒｌｄ［Ｊ］．Ｎａｔｕｒｅ，２０００，４０６，
［４］ＨｅｌｍｙＡ，Ｇａｒｇｓ，ＰａｍｕＰ，ｅｔａｌ＿ｃｏｎｔａｃｔ—ｂａｓｅｄａｒｃｈｉｔｅｃｔｕｒｅｆｏｒ
ｒｅｓｏｕｒｃｅ
ｄｉｓｃｏｖｅｒｙ（ＣＡＲＤ）ｉｎｌａｒｇｅｓｃａｌｅＭＡＮｅｔｓ，ＩＥＥＥ／ＡＣＭ
ＩＰＤＰＳ
Ｉｎｔｅｒｎａｔ．Ｗｏｒｋｓｈｏｐ
ｏｎ
Ｗｉｒｅｌｅｓｓ，ＭｏｂｉｌｅａｎｄＡｄＨｏｃ
Ｎｅｔ—
ｗｏｒｋｓ（ＷＭＡＮ），２００３，２１９—２２７．［５］ＨｅｌｍｙＡ，Ｇａｒｇｓ，Ｐａｍｕ
Ｐ，ｅｔ
ａ１．ｃＡＲＤ：Ａｃｏｎｔａｃｔ—ｂａｓｅｄＡｒ—
ｃ
ｈｉｔｅｃｔｕｒｅｆｏｒＲｅｓｏｕｒｃｅＤｉｓｃｏｖｅｒｙｉｎＡｄＨｏｃ
Ｎｅｔｗｏｒｋｓ［Ｊ］．ＡｃＭ
ＢａｌｔｚｅｒＭｏｂｉｌｅＮｅｔｗｏｒｋｓ
ａｎｄ
Ａｐｐｌｉｃａｔｉｏｎｓ（ＭＯＮＥＴ）
Ｊｏｕｒｎａｌ，
Ｋｌｕｗｅｒ
ｐｕｂｌｉｃａｔｉｏｎｓ，Ｓｐｅｃｉａｌ
ｉｓｓｕｅ
ｏｎ
ＡｌｇｏｒｉｔｈｍｉｃＳｏｌｕｔｉｏｎｓｆｏｒ
Ｗｉｒｅｌｅｓｓ，Ｍｏｂｉｌｅ，ＡｄＨｏｃａｎｄＳｅｎｓｏｒＮｅｔｗｏｒｋｓ，２００５，９９—１１３．［６］ＩｎｔａｎａｇｏｎｗｉｗａｔＣ，ＧｏｖｉｎｄａｎＲ，ＥｓｔｒｉｎＤ，ｅｔａ１．Ｉ）ｉｒｅｃｔｅｄｄｉｆｆｕｓｉｏｎ
ｆｏｒｗｉｒｅｌｅｓｓ
ｓｅｎｓｏｒ
ｎｅｔｗｏｒｋｉｎｇ［Ｊ］．ＩＥＥＥ／ＡｃＭＴｒａｎｓ．
ｏｎ
Ｎｅｔ—
ｗｏｒｋｉｎｇ，２００３，１ｌ（１）：２一１６．
［７］ｃｕｌｌｅｒ
Ｄ，Ｅｓｔｒｉｎ
Ｄ，ｓｒｉｖａｓｔａｖａＭ．Ｇｕｅｓｔｅｄｉｔｏｒｇｉｎｔｒｏｄｕｃｔｉｏｎ：ｏｖｅｒ—
ｖｉｅｗｏｆ
ｓｅｎｓｏｒ
ｎｅｔｗｏｒｋｓ口］．ＩＥＥＥｃｏｍｐｕｔｅｒ，２００４，３７（８）．
［８］ＩｎｔａｎａｇｏｎｗｉｗａｔＣ，ＥｓｔｒｉｎＤ，Ｇｏｖｉｎｄａｎ
Ｒ，ｅｔ
ａ１．Ｉｍｐａｃｔｏｆｎｅｔｗｏｒｋ
ｄｅｎｓｉｔｙ
ｏｎ
ｄａｔａ
ａｇｇｒｅｇａｔｉｏｎ
ｉｎｗｉｒｅｌｅｓｓ
ｓｅｎｓｏｒ
ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃ
２２ｎｄＩｎｔ’１ｃｏｎｆｏｎ
Ｄｉｓｔ“ｂｕｔｅｄｃｏｍｐｕｔｉｎｇｓｙｓｔｅｍ［ｃ］．
Ｖｉｅｎｎａ，
ＩＥＥＥ。２００２．
［９］ＫｉｍＹ，ＨｅｌｍｙＡ，ＳｗＡＴ：ｓｍａｌｌｗｏｒｌｄ—ｂａｓｅｄａｔｔａｃｋｅｒｔｒａｃｅｂａｃｋ
ｉｎ
Ａｄ—ｈｏｃ
Ｎｅｔｗｏｒｋｓ［Ａ］．ＩＥＥＥ／ＡｃＭＭｏｂｉｑｕｉｔｏｕｓｃｏｎｆｅｒｅｎｃｅ
ｒＣ］．２００５．
基于小世界的无线传感器网络资源查询机制
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
刘志强， 蒋泽军， 王丽芳， 王珺吉， 王高祖， 姜华， Liu Zhiqiang， Jiang Zejun， Wang Lifang， Wang Junji， Wang GaoZu， Jiang Hua西北工业大学,陕西,西安,710072计算机测量与控制
COMPUTER MEASUREMENT & CONTROL2006,14(12)2次
参考文献(9条)
1.Helmy A Architectural framework for large-scale multicast in mobile ad hoc networks[外文会议] 20022.Watts D;Strogatz S Collective dynamics of small-world networks[外文期刊] 19983.Kleinberg J Navigating in a smallworld 2000
4.Helmy A;Garg S;Pamu P Contact-based architecture for resource discovery (CARD) 2003
5.Helmy A;Garg S;Pamu P CARD:A Contact-based Architecture for Resource Discovery in Ad Hoc Networks2005
6.Intanagonwiwat C;Govindan R;Estrin D Directed diffusion for wireless sensor networking[外文期刊]2003(01)
7.Culler D;Estrin D;Srivastava M Guest editors' introduction:overview of sensor networks 2004(08)8.Intanagonwiwat C;Estrin D;Govindan R Impact of network density on data aggregation in wirelesssensor networks[外文会议] 2002
9.Kim Y;Helmy A SWAT:small world-based attacker traceback in Ad-hoc Networks 2005
本文读者也读过(5条)
1. 高杨.史丽萍.吴旭东.张增生.温泉.GAO Yang.SHI Li-ping.WU Xu-dong.ZHANG Zeng-sheng.WEN Quan 基于最小二乘支持向量机的振动传感器故障诊断[期刊论文]-机械与电子2009(5)
2. 陈果.李庆华.CHEN Guo.LI Qing-hua 一种利用分布式GA的传感器网络资源管理方法[期刊论文]-电脑与信息技术2010,18(4)
3. 赵志霞.肖德宝.熊磊.徐慧.刘会芬 基于多Agent和策略的无线传感器资源分配模型研究[会议论文]-20074. 吴德会.杨世元.董华.Wu Dehui.Yang Shiyuan.Dong Hua 基于最小二乘支持向量机的传感器动态系统辨识方法[期刊论文]-电子测量与仪器学报2006,20(6)
5. 朱敬华.高宏.ZHU Jing-Hua.GAO Hong 无线传感器网络中能源高效的任务分配算法[期刊论文]-软件学报2007,18(5)
引证文献(2条)
1.王波.杨永明.汪金刚.庄雄.魏欣 基于PSoC的无线传感器网络节点设计[期刊论文]-传感技术学报 2009(3)2.袁宜峰.凌志浩.曹建福 基于记忆的无线 Ad Hoc 网络资源发现方法[期刊论文]-青岛科技大学学报（自然科学版） 2012(5)
本文链接：http://d.wanfangdata.com.cn/Periodical_jsjzdclykz200612057.aspx