An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA Networks
The broadcast scheduling is of fundamental importance and practical concern for ad hoc network performance measures such as the communication delay and the throughput. The scheduling problem on hand involves determination of a collision-free broadcast schedule with the minimum length TDMA frame and...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2008-01-01
|
| Series: | Journal of Computer Systems, Networks, and Communications |
| Online Access: | http://dx.doi.org/10.1155/2008/712126 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832551840353353728 |
|---|---|
| author | Imtiaz Ahmad Buthaina Al-Kazemi A. Shoba Das |
| author_facet | Imtiaz Ahmad Buthaina Al-Kazemi A. Shoba Das |
| author_sort | Imtiaz Ahmad |
| collection | DOAJ |
| description | The broadcast scheduling is of fundamental importance and practical concern for ad hoc network performance measures such as the communication delay and the throughput. The scheduling problem on hand involves determination of a collision-free broadcast schedule with the minimum length TDMA frame and the maximum slot utilization by efficient distribution of slots among stations. The problem is widely known as NP-complete, and diverse heuristic algorithms were reported to solve this problem recently. The intractable nature of the broadcast scheduling problem and its importance in ad hoc TDMA networks necessitates development of more efficient heuristic algorithms. In this paper, we developed a new heuristic approach which employs a tight lower bound derived from the maximal incompatibles and generates a search space from the set of maximal compatibles. The developed algorithm is very efficient and effective in conquering the intractable nature of the broadcast scheduling problem in the sense that it explores complex solution space in smaller CPU time. A comparison with existing techniques for the test examples reported in the literature shows that our algorithm achieves a collision-free broadcast with minimum frame length and the maximum slot utilization in relatively shorter time. |
| format | Article |
| id | doaj-art-e17785e339a44c99b63c57ca018a6bf3 |
| institution | Kabale University |
| issn | 1687-7381 1687-739X |
| language | English |
| publishDate | 2008-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Computer Systems, Networks, and Communications |
| spelling | doaj-art-e17785e339a44c99b63c57ca018a6bf32025-02-03T06:00:29ZengWileyJournal of Computer Systems, Networks, and Communications1687-73811687-739X2008-01-01200810.1155/2008/712126712126An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA NetworksImtiaz Ahmad0Buthaina Al-Kazemi1A. Shoba Das2Department of Computer Engineering, Kuwait University, P.O. Box 5969, Safat 13060, KuwaitDepartment of Computer Engineering, Kuwait University, P.O. Box 5969, Safat 13060, KuwaitDepartment of Computer Engineering, Kuwait University, P.O. Box 5969, Safat 13060, KuwaitThe broadcast scheduling is of fundamental importance and practical concern for ad hoc network performance measures such as the communication delay and the throughput. The scheduling problem on hand involves determination of a collision-free broadcast schedule with the minimum length TDMA frame and the maximum slot utilization by efficient distribution of slots among stations. The problem is widely known as NP-complete, and diverse heuristic algorithms were reported to solve this problem recently. The intractable nature of the broadcast scheduling problem and its importance in ad hoc TDMA networks necessitates development of more efficient heuristic algorithms. In this paper, we developed a new heuristic approach which employs a tight lower bound derived from the maximal incompatibles and generates a search space from the set of maximal compatibles. The developed algorithm is very efficient and effective in conquering the intractable nature of the broadcast scheduling problem in the sense that it explores complex solution space in smaller CPU time. A comparison with existing techniques for the test examples reported in the literature shows that our algorithm achieves a collision-free broadcast with minimum frame length and the maximum slot utilization in relatively shorter time.http://dx.doi.org/10.1155/2008/712126 |
| spellingShingle | Imtiaz Ahmad Buthaina Al-Kazemi A. Shoba Das An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA Networks Journal of Computer Systems, Networks, and Communications |
| title | An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA Networks |
| title_full | An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA Networks |
| title_fullStr | An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA Networks |
| title_full_unstemmed | An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA Networks |
| title_short | An Efficient Algorithm to Find Broadcast Schedule in Ad Hoc TDMA Networks |
| title_sort | efficient algorithm to find broadcast schedule in ad hoc tdma networks |
| url | http://dx.doi.org/10.1155/2008/712126 |
| work_keys_str_mv | AT imtiazahmad anefficientalgorithmtofindbroadcastscheduleinadhoctdmanetworks AT buthainaalkazemi anefficientalgorithmtofindbroadcastscheduleinadhoctdmanetworks AT ashobadas anefficientalgorithmtofindbroadcastscheduleinadhoctdmanetworks AT imtiazahmad efficientalgorithmtofindbroadcastscheduleinadhoctdmanetworks AT buthainaalkazemi efficientalgorithmtofindbroadcastscheduleinadhoctdmanetworks AT ashobadas efficientalgorithmtofindbroadcastscheduleinadhoctdmanetworks |