继电器
无线传感器网络
计算机科学
中继信道
无线传感器网络中的密钥分配
计算机网络
节点(物理)
传输(电信)
传感器节点
无线
拓扑(电路)
无线网络
功率(物理)
数学
电信
工程类
组合数学
物理
结构工程
量子力学
作者
Jonathan R. Lloyd,Xiao Xue
标识
DOI:10.1109/tc.2007.250629
摘要
A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy consumption is a superlinear function of the transmission distance. One approach to prolonging network lifetime while preserving network connectivity is to deploy a small number of costly, but more powerful, relay nodes whose main task is communication with other sensor or relay nodes. In this paper, we assume that sensor nodes have communication range r>0, while relay nodes have communication range Rgesr, and we study two versions of relay node placement problems. In the first version, we want to deploy the minimum number of relay nodes so that, between each pair of sensor nodes, there is a connecting path consisting of relay and/or sensor nodes. In the second version, we want to deploy the minimum number of relay nodes so that, between each pair of sensor nodes, there is a connecting path consisting solely of relay nodes. We present a polynomial time 7-approximation algorithm for the first problem and a polynomial time (5+epsi)-approximation algorithm for the second problem, where epsi>0 can be any given constant
科研通智能强力驱动
Strongly Powered by AbleSci AI