Optimal Relay Placement For Indoor Sensor Networks

Wireless sensor networks have been increasingly deployed in differentenvironments for various useful applications. A distinguishing feature ofsensor networks is possible dense deployment of low-cost and low-powersensor nodes. To many sensor networks, the robust operation depends ondeploying relays to ensure wireless coverage. This paper considers the crucialproblem of optimal relay placement for wireless sensor networks in indoorenvironments.The placement of relays is essential for ensuring communication qualityand data collection. In order to enable efficient communication of sensedinformation among nodes and the sink, a number of wireless relays can bedeployed to reduce energy consumption and prolong system lifetime, whichmeans the range of coverage should be as large as possible. In order toguarantee the communication quality between the wireless sensor sender andreceiver, it needs to ensure connectivity between nodes while meets thecoverage rate requirement. Sometimes in order to reach the connectivityamong nodes, it is usually not enough only by wireless sensor nodesthemselves. The solution is to add a kind of additional wireless sensor nodescalled relay, which is used to transmit the data between common sensor nodes.These relays makes the entire network has a smaller energy consumption andalso a longer system lifetime. Because the importance of the relays, we needto find an appropriate placement method to decide the location of both thewireless sensor nodes and the relay nodes.The main content of this study is how to make a wireless sensor networkachieve the optimal deploy pattern of relays in a given indoor environment.This problem owns significant practical meaning. The objective is to deploythe minimum number of relays such that most sensor nodes deployed at anyplace within the environment can communicate with at least one relay node. In this way, for an arbitrary deployment of sensor nodes it is guaranteed mostsensor nodes can communicate with a relay node. It is highly desirable that aminimum number of relays be deployed because a relay node has highercapability and hence usually requires higher cost compared with otherregular sensor nodes.A number of research efforts have been made for computing thedeployment locations of relay nodes in wireless sensor networks.Unfortunately, these efforts have assumed that the target sensor network isdeployed in an ideal environment where the radio coverage of a sensor nodecan be modeled as a unit disk. This assumption is easily becomes invalidwhen sensor networks are deployed in an indoor environment The radiopropagation model in an indoor environment is more complex than in anoutdoor environment. Obstacles like walls may significantly degrade radiostrength as a radio signal goes through the obstacles. As a result, suchcomplex environments make these existing solutions inapplicable to relayplacement for sensor network in indoor environments.In addition, many algorithms for sensor node placement to achieve fullsensing coverage have been proposed. If we treat the radio transceiver as aspecial sensing device and the radio coverage as the sensing range, it ispossible to find a feasible relay placement in the given environment.However, these algorithms for full sensing coverage again assume uniformsensing coverage, i.e., the sensing coverage is a unit disk. Thus, thesealgorithms cannot be applied for relay node placement in indoorenvironment.As the radio coverage of a relay node in a complex indoor environmentcan no longer be assumed as a regular disk, it becomes highly challenging todetermine the minimum number of required relays and to compute theirdeployment locations. We explicitly take walls in the indoor environment intoaccount. A wall based propagation model is used to predict the radio coverageof a given relay node. We then propose an efficient greedy algorithm calledRPI to compute the deployment locations of the relays. We firstly theoretically prove that the indoor relay placement problem isNP-hard. We then predict radio coverage of a given relay deployment inindoor environments, and then propose an efficient greedy algorithm forcomputing the relay deployment locations for required coverage quality. Toour knowledge, our work is the very first that study the optimal relayplacement problem for sensor networks in complex indoor environments.