Efficient Scheduling for Video Transmissions in Maritime Wireless Communication Networks
Authors:
- 1 October 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Vehicular Technology
- Vol. 64 (9) , 4215-4229
Abstract
This paper develops a framework for vessel surveillance video uploading via maritime wideband communication networks. A broadband wireless network utilizing a time-division-multiple-access (TDMA)-based media access control protocol is employed to establish a shore-side network infrastructure, and a packet store-carry-forward routing mechanism is adopted to achieve intermittent network connectivity in maritime communications. To provide high-quality videos to the administrative authority, a resource allocation problem is formulated to maximize the throughput priority-based video transmission problem, subject to the intermittent network connections and the time indexes such as the release time and deadline of each video packet. To reduce computational complexity, time-capacity mapping is applied to transform the original resource allocation problem into a two-machine nonpreemptive scheduling problem. Three offline scheduling algorithms are proposed, namely, a time-capacity-mapping-based two-phase (TMTP) algorithm for a single machine, a TMTP algorithm for two machines, and an interval graph-theory-based job relay selection (IGTJRS) algorithm. It is mathematically proved that the IGTJRS algorithm has an approximation ratio (i.e., the ratio of the throughput of an optimal schedule to that of the IGTJRS algorithm) of 2 and time complexity of O(n 2 ). Simulations results validate the performance of the proposed algorithms, based on real ship route traces obtained from navigation software BLM-Shipping.Keywords
Funding Information
- China Postdoctoral Science Foundation (2013M530900)
- Natural Science Foundation of China (61401057)
- Science and Technology Research Program of Liaoning (L2014213)
- Natural Sciences and Engineering Research Council of Canada
- Research Funds for the Central Universities
- China Postdoctoral International Academic Exchange Fund
- Scientific Research Foundation for the Returned Overseas Chinese Scholars
This publication has 32 references indexed in Scilit:
- Throughput Maximization in Mobile WSN Scheduling with Power Control and Rate Selection2012
- Who, When, Where: Timeslot Assignment to Mobile ClientsIEEE Transactions on Mobile Computing, 2011
- The Electronic Chart Display and Information System (ECDIS): An Operational Handbook2009
- Capacity Enhancement using Throwboxes in DTNs2006
- Knapsack Problems2004
- Multi-phase Algorithms for Throughput Maximization for Real-Time SchedulingJournal of Combinatorial Optimization, 2000
- Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problemAnnals of Operations Research, 1994
- Chapter 9 Sequencing and scheduling: Algorithms and complexity1993
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphsInformation Processing Letters, 1992
- A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobsAnnals of Operations Research, 1990