Scheduling with slack time

Summary We consider a scheduling problem concerning a set of jobs {J ₁, J ₂,..., J _n } in which the job J _i requests C _i units of computation time every T _i units of time periodically. These jobs are to be executed by a timeshared single-processor computing system. It is assumed that the requests for each job arrive at the system at the beginning of the request periods and that deadline for completion of the requested computation in each period coincides with the beginning of the next period. For a set of jobs that is schedulable by a certain algorithm, the time span between the completion of a request and its deadline is referred to as the slack time of the request. It is shown here that when the set of jobs is scheduled according to the rate monotonic algorithm, the slack time of the first request of any job is no larger than the slack time of any subsequent request of that job. This result enables us to determine lower bounds to slack times of all requests.This work was partially supported by the Office of Naval Research under the Contract Number N00014-79-C-0775 and by NSF-MCS-8107647     

Network communication in edge-colored graphs: gossiping

A mechanism for scheduling communications in a network in which individuals exchange information periodically according to a fixed schedule is presented. A proper k edge-coloring of the network is considered to be a schedule of allowed communications such that an edge of color i can be used only at times i modulo k. Within this communication scheduling mechanism, the information exchange problem known as gossiping is considered. It is proved that there is a proper k edge-coloring such that gossip can be completed in a path of n edges in a certain time for n⩾k⩾1. Gossip can not be completed in such a path any earlier under any proper k edge-coloring. In any tree of bounded degree Δ and diameter d, gossip can be completed under a proper Δ edge-coloring in time (Δ-1)d +1. In a k edge-colored cycle of n vertices, other time requirements of gossip are determined     

A hierarchical energy-efficient framework for data aggregation in wireless sensor networks

A network of sensors can be used to obtain state-based data from the area in which they are deployed. To reduce costs, the data, sent via intermediate sensors to a sink, are often aggregated (or compressed). This compression is done by a subset of the sensors called "aggregators." Inasmuch as sensors are usually equipped with small and unreplenishable energy reserves, a critical issue is to strategically deploy an appropriate number of aggregators so as to minimize the amount of energy consumed by transporting and aggregating the data. In this paper, the authors first study single-level aggregation and propose an Energy-Efficient Protocol for Aggregator Selection (EPAS) protocol. Then, they generalize it to an aggregation hierarchy and extend EPAS to Hierarchical EPAS. The optimal number of aggregators with generalized compression and power-consumption models was derived, and fully distributed algorithms for aggregator selection were presented. Simulation results show that the algorithms significantly reduce the energy consumption for data collection in wireless sensor networks. Moreover, the algorithms do not rely on particular routing protocols and are thus applicable to a broad spectrum of application environments.