Robot and Sensor Networks Lab

Mobility Management and Control for Mobile Data Collectors

Availability of the tiny, low-cost micro electro-mechanical systems has enabled the collocated use of wireless devices equipped with sensing capabilities in order to form a network. Emergence of the Wireless Sensor Network (WSN) applications (i.e., forest fire detection, battlefield surveillance, landslide detection) where the data to be used is mostly known in a priory has paved the way for the development of the concepts such as smart homes, smart cities, and smart grid recently thanks to the smart phones, music players, gaming systems, and even medical devices equipped with several sensors. Small form factor of the devices limits on board batteries and thus requiring employment of the communication protocols with shorter transmission ranges (i.e., Bluetooth, IEEE 802.15.4, 6LoWPAN, etc.) in order to prolong the lifetime. Besides, for a smart phone, as an example, it may be more desirable to use Bluetooth, despite the availability of protocols supporting communication over longer distances such as IEEE 802.11, IEEE 802.16e/m, etc. due to varying reasons including user preferences, energy cost, communication cost, etc. No matter which protocol is in use, there is always a limit on the transmission range. The novel approaches to be developed during this project is going to enable communication between devices apart from each other longer than their transmission ranges. Through exploiting mobile data collectors (MDCs), it will be possible to collect the data and move it towards its destination and provide intermittent network connectivity. Thanks to the nature of this approach, the solutions to be developed will not be dependent on a particular protocol or technology but will be applicable to problems from nano size to macro size based on the scale to be considered.

The problem of determining the optimal path, which visits the given locations, can be modeled as the traveling salesman problem (TSP). But unlike TSP where the exact locations to be visited is available, visiting the node location is not necessary to communicate with a wireless node. Instead, to establish communication, it is sufficient to be located anywhere within the transmission range of the node. Furthermore, in the considered problem, both individual nodes as well as networks which consists of multiple nodes may have to be visited. To determine the stopping point to collect the data from the network, one must consider the area defined by the intersection of the given nodes’ communication ranges. Also, it should be noted that nodes at different stopping points may generate data with different frequencies. Therefore, the amount of data to be collected may vary based on the region. Besides, speed and energy consumption may be different across different regions due to the varying terrain types and obstacles. Thus, the most cost efficient route along with the stopping points must be determined for the MDC considering the defined requirements. It should be noted that it might not be possible to satisfy the given requirements by employing single MDC. In such a case, multiple MDCs may exist in the network. But, this complicates the problem even further due to the load balancing and synchronization issues that arise. Novel clustering algorithms will be developed to distribute the load among the MDCs evenly. Considering their limited batteries, battery depletion of the MDCs will be ensured to occur around the same. This will avoid premature battery depletion of one or more MDCs due to excessive load, which impairs the solution. Existence of multiple MDCs in a network requires their collaboration to pass data. To relay data, two or more MDCs may need to stop at the meeting points and wait for their pairs. To minimize the waiting time at the meeting points and to ensure such meetings, MDCs must be synchronized and their movements must be according to a certain schedule. Albeit some solutions for some of the mentioned problems, no relevant solution exists in the literature which considers the problem with the defined constraints. For instance, as part of the operations research, facility location problem clusters the given points to minimize the total travel cost. Our problem, on the other hand, demands a clustering algorithm to distribute the travel costs evenly. While, more than one salesman is allowed in the multiple traveling salesman problem (mTSP), unlike our problem, tours of the salesmen start and end at the depot and exact locations to be visited are available. Covering salesman (CSP) identifies the minimum cost tour where the points not on the tour must be within the covering distance of the visited points. However, our problem is to determine fairly distributed multiple paths without the availability of exact locations to be visited. The novel solutions to be developed using linear programming and heuristic approaches for our NP-hard problem during the project will close the gap in this field and foster new studies.