D-TDMA: a New Dynamic TDMA Protocol
with High Throughput
Song Bao-hua, Yang Ping, Wang Wen-qi
Abstract: This paper presents a new dynamic TDMA protocol. In this protocol, free slots are full used for the slot request of nodes. By this way, slots are wasted lest and resource is imposed adequately. In result, the protocol shows a good throughput performance.
Keywords: TDMA, Dynamic TDMA, Medium Access Control
1. Introduction
The traditional TDMA protocol allocates fixed slots to fixed nodes, which means the MAC (Medium Access Control) protocol can’t support the dynamic entering and quitting and can’t support to create a communication system which contains nodes more than the quantity of slots in a frame. Some dynamic TDMA protocols[1-3] are proposed to resolve this problem. Based on thinking in these protocols, this paper designs a new dynamic TDMA protocol which has the advantages of all these protocols and provides high throughput.
2. Slot Config
|
SOF
|
CSSSi
|
Si1
|
Si2
|
Si3
|
Si4
|
Si5
|
…
|
SiM
|
SOF：Head flag used for synchronizing frames
CSSSi：The slot for master node to send packet of slot assign Pslot_allot
Sij：The jth slot of the ith frame
M：The max slot number considering the ability to supply real-time
IMAGE 1 Slot Config in a Single Frame
3. Function of Master Nodes
3.1 Allocate Slots
The master node keeps up with a slot assignment table(table 1),which records the status of every slot, and is updated with the request of slave nodes.
TABLE 1 Slot Assignment Table
|
sequence number
of slots
|
status
|
address of
the node sending
|
address of
the node receiving
|
|
1
|
idle / busy
|
000001
|
000010
|
|
2
|
idle / busy
|
000010
|
000001
|
|
…
|
…
|
…
|
…
|
|
M
|
idle / busy
|
000011
|
000100
|
The maser node supervises a queue which records the request information of slave nodes (image 1). The request information includes the address of the node which requested slots and the amount needed.
IMAGE 2 Slot Request Queue
As a master node, it is always listening to the packets being sent in the network. When it hears a slot request packet sent by any slave node in any idle slot, it will add the request information into the tail of the slot request queue.
At the beginning of every frame, the maser node will analysis the information recorded in the head of the slot request queue. Assuming the quantity of slots requested is nreq according to the head of the slot request queue and the network still leaves Sfree free slots, the master node will deal with the request in the head as the following.
1.
IF Sfree >= nreq THEN
2.
allot the first nreq free slots to the slave node
3. eliminate the current head of the slot request queue
4. take out the new head of the slot request queue, and jump to 1
5. END IF
3.2 Notice Slave Nodes
In the CSSSi slot, master nodes will broadcast the Pslot_allot packet to announce the status of every slot in the frame. The Pslot_allot packet is like image 3.
|
P
|
F
|
Ai1
|
Ai2
|
Ai3
|
…
|
AiM
|
L
|
A1
|
…
|
|
FCS
|
F
|
P: Sequence to start and synchronize the modem
Aij: Address of the node authorized to send packets in the jth slot of the ith frame. If no node obtains the slot, it will be 0.
FCS: Frame checkout sequence
F: Frame flag. The content between two frames flag constitutes a frame
L: Amount of nodes not given slots even though their slot request packets were heard
Ai…
A
L
: addresses of nodes not given slots even though their slot request packets were heard
IMAGE 3 Formats of Slot Allocation Packets
3.3 Release Slots
Master nodes will release the slots allocated to a node in the following two cases.
Active Release
Active release means the master node in a network will release the slots authorized to a slave node automatically when it hears the slot release packet sent by the slave node.
Passive Release
Passive release means the master node in a network will also release the slots authorized to a slave node when it hasn’t heard any packet sent by the slave node over three times.
4. Function of Slave Nodes
Like the master node, every slave node keeps a table called slot status table(table 2) which also records the status of all slots. But the different is the information in the table includes the serial number of slots, the status of slots, which is busy or idle, and a Boolean variable denoting whether the slot is allocated to the slave node itself.
The slot status table is also refreshed whenever the slave node hears a Pslot_allot packet which hints the change in the status of any slot.
TABLE 2 Slot Status Table
|
sequence number
of slots
|
status
|
whether the slot is allocated to the node itself
|
|
1
|
busy / idle
|
Y/N
|
|
2
|
busy / idle
|
Y/N
|
|
…
|
…
|
…
|
|
M
|
busy / idle
|
Y/N
|
4.1 Request Slots
If the user process of a slave node wants to request some slots to send information to another node, it will check the slot status table to find out whether there is any idle slot to send slot request packet. If there are still Sfree slots free for the slave node to request, the slave will produce a stochastic natural number between 1 to Sfree and send the slot request packet in the particular slot corresponding to the stochastic number. The relationship between the slot to send slot request packet and stochastic number is like image 4.
IMAGE 4 Slots to Send Slot Request Packets
In the CSSSi slot of the next frame next to which in the slave node sends a slot request packet, the same slave node will analysis the Pslot_allot broadcasted by
the master node to find out whether the slot request packet is heard by the master successfully. In the best situation, which means the request packet is heard and slots needed are given, the slave node will send information in the corresponding slots. But if the slots it requests are not attained, the slave node will wait until the master node releases some busy slots and allocates some to it. In the worst situation, which means the slot request is even not heard, the slave node will send another slot request packet according to the arithmetic described in the above paragraphs in the current frame.
4.2 Send and Receive Packets
In the process of requesting slots, the slave node will send a slot request packet. And in the allocated slots for sending data packets, the slave node will send data packets. When the packets are sent over and the slave node doesn’t need the slots given to it, it will send a slot release packet in the slot for sending data. The format of all the three types of packets, data packets, slot request packets and slot release packets, are same (Image 5), and they are differentiated only by a control field in packets.
|
P
|
F
|
AS
|
Ad
|
Control
|
L
|
Data
|
FCS
|
F
|
As: The address of the source node
Ad: The address of the destination node
Control: Control information
L:The length of data for data packets;
The quantity the slave requests for slot request packets
Data:Valid payload for data packets
IMAGE 5 Slot Request Packets and Data Packets
5. Performance Analysis
Image 6 presents the throughput changing with the number of nodes which join the competition of slots. 1 means all slots are impropriated. In the simulation, the total slot number is 10.
IMAGE 6 Throughput changing with nodes increasing
According to image 6, throughput increases with the increasing of the number of nodes when the number is less. Then, when the number is more than a greater value, the throughput will reduce with the increasing of the number of nodes due to the increasing competition collision. The trend is the same with other protocols based on competition, such as CSMA/CA[4], CSMA/CD[5] etc.
Reference
[1] Georgios I. Papadimitriou, et al. Self-Adaptive TDMA protocols for WDM star networks: a learning-automata-based approach[J]. IEEE Photonics Technology Letters, 1999,11(10):1322-1324
[2] Zhang Jun, Zhang Qishan, Deng Qiulin. On the slot reservation selection algorithm about self-organized TDMA VHF data link [J]. Journal of Beijing University of Aeronautics and Astronautics, 2001,27(5):514～517
[3] Johnsson L. The cellular CNS concept ( CCC) operating concept based on the VHF STDMA data link [ J ] . Navigation , 1996 , 44(176):432～459
[4] IEEE Computer Society. IEEE 802.3 Carrier sense multiple access with collision detection(CSMA/CD) access method and physical layer specifications[G]. The Institute of Electrical and Electronics Engineers, Inc. 2002
[5] IEEE. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Standard 802.11. 1999
本文转自 21cnbao 51CTO博客，原文链接：http://blog.51cto.com/21cnbao/120267，如需转载请自行联系原作者
