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

摘要

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