Greedy Extension of Localized Auction Based Protocols for Wireless Actuator Task Assignment
Ivan Mezei, Veljko Malbasa and Ivan Stojmenovic
In this paper we assume that all actuators are mobile and an event was reported to one of the actuators, and a response by one actuator is required. The goal of actuator task assignment is to select the best actuator for responding to a reported event so that communication cost for selecting, and response time for performing the task are minimized. Existing solutions, except those proposed in [3] for robot networks, are usually either centralized, neglecting communication cost, assuming complete graph, or based on flooding with individual responses to actuator decision maker (simple auction protocol – SAP), ignoring communication cost and response time bound. This article proposes greedy improvement to previously proposed (in [3]) k-hop simple auction protocol (k-SAP) and k-hop simple auction aggregation protocol (k-SAAP) for task assignment in multi-hop wireless actuator networks. After decision about the best actuator is made by k-SAP or k-SAAP, new 1-SAP greedy auction is initiated by that actuator in order to search for possibly better actuator in 1-hop neighborhood. Such greedy approach proceeds until no better actuator is found. Improvement of new k-SAPG and k-SAAPG over k-SAP and k-SAAP by applying greedy approach is shown by simulation results.
Keywords: Greedy algorithm, localized auctions, task assignment, wireless sensor and actuator networksy