| 摘要: |
| 由于无线传感器网络通信的不稳定性及地理环境的复杂性,传感器节点间经常出现地理位置相近但连通概率却很低的情况.在网络中快速发现通信质量好的节点集以及内部相互联系紧密的子区域,对于传感器网络中的节点分簇、路由优化等具有重要作用.使用不确定图挖掘技术研究如何从一个不确定的无线传感器网络拓扑结构中,快速发现联系紧密且存在概率高的不重叠连通区域问题.提出K-CLOSE算法,首先,使用分布式方法将无线传感 器网络的拓扑结构构建为不确定图;然后,提出一种近似比为2的近似算法来计算紧密阈值;最后,通过构建搜索树并使用剪枝等方法快速发现顶点相互联系紧密且存在概率高的不重叠连通区域.实验结果表明,K-CLOSE算法可以高效地发现无线传感器网络中的紧密连通区域. |
| 关键词: 无线传感器网络 不确定图 数据挖掘 紧密区域 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金(61033015,60831160525,60933001,61173023);中央高校基本科研业务费专项资金(HIT.NSRIF.201180);黑龙江省研究生创新科研基金(YJSCX2011-239HLJ);黑龙江大学学生学术科技创新项目(2011386,2011387) |
|
| K-CLOSE:Algorithm for Finding the Close Regions in Wireless Sensor Networks Based Uncertain Graph Mining Technology |
|
HAN Meng1, LI Jian-Zhong1,2, ZOU Zhao-Nian2
|
|
1.School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China;2.School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
|
| Abstract: |
| Due to the instability of wireless links and the complexity of geographical environment where wireless sensor networks are deployed,sensor nodes can not guarantee communication with their neighboring nodes with high probabilities.Resolving the problem of finding the sensor nodes that communicate well in practical settings can play an important role in node clustering and the optimization of routing protocols.It is important to note the discovery which nodes in a region are more close to each other in actual movement.A new algorithm called K-CLOSE is proposed in this paper to solve the problem which finding the most k close regions.First,K-CLOSE abstracts wireless sensor networks into uncertain graphs in a distributed manner.Then,the closeness threshold is determined by an approximation algorithm proposed in this paper,which has approximate rate 2.Finally,the k close regions where sensor nodes communicate with high probabilities are discovered using tree searching and branch-and-bound methods.Moreover,the experimental results show that the proposed algorithm is efficient in practice. |
| Key words: wireless sensor networks uncertain graph data mining close region |
