混合无线传感器网络中的网关部署算法  

Gateway Placement Algorithms in Hybrid Wireless Sensor Networks

作　　者：郭雪泉[1] 李建中[1,2] 于博[2] 

机构地区：[1]黑龙江大学计算机科学技术学院,哈尔滨150080 [2]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机研究与发展》2011年第S2期39-44,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金重点项目(61033015);国家自然科学基金项目(60831160525;60933001)

摘　　要：在混合无线传感器网络模型下,提出了最小化网关个数部署问题(MNGP).将MNGP问题形式化地表示为0-1整数线性规划,从而证明了MNGP问题为NP-hard问题.为解决MNGP问题,提出了启发式的网关部署算法(HGPA)和随机网关部署算法(RGPA),分析了2个算法的时间复杂度分别为O(m2n 2)和O(mn2).最后,利用模拟实验验证了这2个算法的性能,分析了候选网关分布、网关流量限制和最大跳数对算法性能的影响.在混合无线传感器网络模型下,提出了最小化网关个数部署问题(MNGP).将MNGP问题形式化地表示为0-1整数线性规划,从而证明了MNGP问题为NP-hard问题.为解决MNGP问题,提出了启发式的网关部署算法(HGPA)和随机网关部署算法(RGPA),分析了2个算法的时间复杂度分别为O(m2n 2)和O(mn2).最后,利用模拟实验验证了这2个算法的性能,分析了候选网关分布、网关流量限制和最大跳数对算法性能的影响.

关 键 词：无线传感器网络 混合网络 网关部署 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]