In the sensor relocation (SR) problem, advertisement packets are used to inform the locations of redundant sensors and request packets are used to inform the locations of requesting places. When redundant sensors move to requesting places, their location information will change. So, the message with redundant sensors information is not reusable. This is also why locating redundant sensors with low message overhead is of high importance. In this paper, we revisit the matching problem of SR in mobile wireless sensor networks. In order to reduce the amount of message exchange, we employ the concept of quorum to send advertisement packets (in columns) and request packets (in rows). With the proposed stopping criteria, the proposed algorithm can further reduce the amount of these two types of packets to send. In performance evaluation, we consider three scenarios of different shapes, including a square plane, a rectangular plane and a circle plane. The simulation results show that the proposed algorithm can effectively and significantly reduce the number of advertisement and request packets to find the optimal (nearest) redundant sensor for each requesting place.
