A Fair-Priority MAC design in Networked Control System

Published Online October 2009 in MECS

With the development of small, low-power, and lowcost devices, researchers have turned to developing hardware and software platforms to support distributed sensing and computation via hundreds or thousands of tiny nodes. Wireless Sensor Networks (WSNs) is composed of theses nodes. In the last several years, many of the foreseen applications and challenges [1] of WSNs have been actively researched. WSNs have already shown their usefulness in many distributed sensing arenas such as monitoring [2], meteorology, information for first responders, and vehicle detection [3]. Several important control applications such as pursuit-evasion game, and robot navigation stand to benefit by the introduction of a sensor network platform. For a control system to benefit from a sensor network platform, the requirement of low latency communication is getting more and more important. Out-of-date information will be irrelevant and may even lead to negative effects to the system

Manuscript received January 16, 2009; revised June 11, 2009; accepted July 21, 2009.

monitoring and control. Very little prior work can be applied directly. New designs are necessary for offering RT quality of service (QoS) in WSNs with guaranteed end-to-end delivery time, delay jitter and other QoS metrics. During the development of such requirements, challenges of real-time services in wireless communication systems are critical for multimedia. This work considers the medium access control (MAC) problem in WSNs. The goal of our work is to design a real-time medium access control protocol that provides multiple priority levels. We guarantee that higher-priority frames are transmitted earlier than lower-priority frames and bounded delay for all the messages.

• II.    Related works

In WSNs, MAC plays a key role in determining the channel access delay, utilization and energy consumption. A considerable research effort has been devoted to WSNs MAC protocols in the last few years. While these protocols focus mainly on energy efficiency. Latency in message delivery is not usually a metric to be optimized. In one of classical categories [4] the existed proposals can be classified: contention-based or TDMA-based. MAC protocols based on contention are simple, scalable and flexible. While the major drawback is a high idle listening time which results in the dominant factor of energy waste. WSNs contention-based proposals presently extend the Carrier Sense Multiple Access/Collision Avoidance mechanism. These protocols use additional schemes to reduce overhearing and idle listening for least energy waste. The SMAC proposed in [5], which is a classic protocol based on contention, provides a tunable periodic active/sleep cycle for sensor nodes. It puts nodes to sleep at certain times to conserve energy. However, periodic sleep may result in long sleep latency since the sending node has to wait until the receiving node wakes up in its listen period. The Timeout-MAC (T-MAC) [6] protocol improves S-MAC by using an adaptive cycle length. The listen/sleep interval duration adapts to traffic fluctuations and obtains a better energy profile. This family of MAC protocols is relatively simple but does not guarantee latency. In contrast, with a similar complexity, our protocol keeps latency bounded. TDMA protocols [7, 13, 14] assign timeslots to nodes, avoiding collisions and idle listening.

By producing a schedule, the MAC protocol clarifies which sensor nodes should utilize the channel at any time and thus limits or eliminate collisions, idle listening, and overhearing. However, these advantages come at the cost of increased messages to create and maintain a schedule. Node mobility, node redeployment, and node death all complicate schedule maintenance. Additionally, some delay exists between the time a sensor node dies and the time neighboring sensor nodes reassign its resources, so some resources may go unused and lead to unnecessary delays or packet loss. Scheduled MAC protocols must also minimize the effect of added latency and limited throughput. Typically, each sensor node can only access the wireless channel for a fraction of the possible time. With a TDMA-based MAC protocol the time a sensor node may access the channel depends heavily on the time slot length. Sensor nodes that wish to transmit messages that is more important than the current reserved time slots can handle must coordinate with other sensor nodes on the schedule to gain access to the extra time slots. Thus, each sensor node must queue messages until it has a chance to transmit them. Several scheduled MAC [8, 12] protocols attempt to overcome the limitations on throughput and latency at the cost of sharing additional information in messages or higher duty cycles. JANG-PING SHEU et al [9] presents a MAC protocol supporting priority in ad hoc networks. Kwang-Jin PAEK et al [10, 11] presents a PQ-MAC that provides a multilevel queue system for priority packet scheduling. Motived by these PQ-MAC protocols we propose a fair medium access control protocol that provides multiple priority levels. The channel is accessed by sensors according to their priorities. Sensors they send frames in a round manner with the same priority. The fairness between different priorities is provided.

• III.    The Proposed Fair Priority MAC(FP-MAC) Protocol

In this section we introduce our fair multi-priority MAC protocol. All the packets with different importance are prioritized into m levels. Higher levels mean higher priorities for transmission. While considering the fairness for the different priority the MAC protocol assigns transmission time according to its priority. For sensors with packets of the same priority, we will order these packets based on the sensor ID number. These sensors will send their packets according to the ID until all packets of the same priority are exhausted in the assigned transmission time. Then sensors with packets of the next priority level will join in transmission when last transmission time is over.

Let give the assumption of the Fair Multi-Priority MAC protocol.

Definition 1: The packets are prioritized into m levels which are respectively p1,p2,L and pm , in addition p1≥p2≥... ≥pm . Without loss of generality, m let∑pi = 1.

i = 1

Definition 2: Sensors with packets of the same priority p_m are classified into Group M ( G_m ).

Definition 3: The time is divided into slots and a slot is defined as τ _p . All the data frames are same in length and the transmission time is τ .

Definition 4: The transmission time of M-Group sensors is assigned as t_m .

• A.    The FP-MAC frame slots assigning algorithm

The FP-MAC Protocol assumes a single, time-slotted channel for both data and broadcast message transmissions. Figure 1 shows the overall time-slot organization of the protocol. Time is organized as sections of random- and scheduled-access periods. We refer to random-access slots as broadcast slots and scheduled-access slots as data transmission slots. A frame time is set as T slots. The broadcast slots are T ₁ and data transmission slots are T ₂ . T ₂ is divided into t ₁, t ₂ L t_m , and the sun of t , t L t is T . The Group M sensors can 12 m 2

transmit datum only in the t_m slots. Considering the priority p_m we set t_m as following:

Figure 1. FP-MAC Frame Format

• B.    The channel access algorithm

Sensors propagate one-hop neighbor information among neighboring nodes during the random access period using the broadcast slots. During the broadcast period, nodes perform contention based channel acquisition and thus signaling packets are prone to collisions. Sensors gather neighborhood information by exchanging broadcast packets during the random access period. The packets include the data priority and its own ID number. Figure 2 shows the format of the header of a broadcast packet. Sensor receives broadcast packets that carry neighborhood information and saves the neighborhood ID. After obtaining information the sensor in the same priority pm begins to compute the order Gmn in all sensors according to the ID number, such as theG sensor is the n-th sensor with the ID number from mn the minimum to the maximum in the group Gm . At the end of random access period all sensors get a unique order in its own priority group.

In the scheduled-access slots, as data transmission slots, the sensor begin to enter the transmission period. At the beginning of tm slots the minimum order sensor in the group Gm transmits packets first. Then the other sensors will transmit their frames in a round-robin manner. The order that sensors transmit can be in an ascending order of their G numbers. Ift slots are out the sensor of the mn                  m current group must give the access chance to the sensor from the next group. When the maximum order sensor of group Gm with the priority pm has finished transmitting the maximum order sensor will broadcast a beginning packet to the next group Gmif the tm slots are still not out. The whole channel access algorithm is presented as following.

Algorithm1. Pseudo-code description of channel access algorithm

• 1    compute the G_mn for all sensors, t_m for group G_m .

• 2    For (priority level=1:m)

• 3    {IF (the sensor with minimum G_mn receives beginning broadcast from G m 1 OR t m begin

• 4   {For ( G_mt =1:n)

• 5      { If ( t_m slots are not out)

• 6       { transmit data;

• 7    If (t=n AND G slots is less than t slots) mn                        m

• 8              { broadcast a beginning packet to

the G m + 1 };

• 9         }

• 10    }

• 11    }

• 12    }

• C.    Scheduling for sensor’s sleep/wakeup period

Most sensor network MAC protocols have some overlap in their effort to limit energy consumption. The most common and effective way to conserve energy places the transceiver and processor into a low power sleep state when the resources have no work to perform. MAC protocols adapt to network conditions may consume a minimum of energy resources while providing responsive performance since they can operate over a range of conditions. Sensor networks that sporadically generate large volumes of traffic provide the best cases for MAC protocols that modify their operation based on traffic conditions. However, to provide this benefit MAC protocols must estimate and share traffic information with neighbors and utilize resources to maintain a current and correct view of the network state. Based on the above analysis and the existed researches the likelihood of k packets arriving over a period can be modeled as a Poisson Process with intensity X . Then the theorem is given below.

Theorem 1. The probability P (nT, t) of k packets arriving over a period from the beginning of n-th MAC r t                 t t '   [X(nT t)]   — XnT-1)

frame to the current time t is              e k!

Where X is the intensity, and t >  nT k = 0,1,2, l , n = 0,1,2, l

.

,

Proof . Let E ( t ) - E ( t 0 ) present the number of arriving packets over the period [ t 0 , t ) considering 0 <  t 0 <  t .

«

Then there is ^ P k ( t 0 , t ) = 1in Poisson Process. First we k = 0

compute the P 0 ( nT , t ) . Considering A t >  0 we get the following function:

P ₀ ( nT , t + A t ) = P { E ( nT , t + A t ) = 0}

= P { E ( nT , t ) = 0, E ( t , t + A t ) = 0}

= P { E ( nT , t ) = 0} P { E ( t , t + A t ) = 0}       ⁽²⁾

= P ₀ ( nT , t ) [1 - XA t + o ( A t ) ]

Equation (2) can be rewritten as

P₀ ( nT , t +A t ) - P₀ ( nT , t ) = -A P ( nT , t ) + o ( A t ) (3)

Let A t be close to zero, equation (3) can be considered as a differential equation of P₀ ( nT , t ) .

dP„ ( nT , t )          ,      .

,     =- X P ( nT , t )

dt

The substituting E ( 1 ₀, 1 ₀ ) = 0 into equation (4) results in equation (5).

P ₀ ( nT , t ) = e ^{-X (} t ^- n ^T ) , 0 <  nT <  t             (5)

Now we compute P k ( nT , t ) , k >  1 »

According to the total probability formula the equation is given as below.

P { E ( nT , t +A t ) = k } = P { E ( nT , t ) + E ( nT , t +A t ) = k }

= ^ P { E ( nT , t +A t ) = i}P{E ( nT , t ) = k - i} i = 0

Similar to the thought of equation (3)-(5), equation (6) can be considered as a differential equation of P k ( nT , t ) when A t is close to zero.

dP ( nT , t )         _{z x z x}

——— = - X P ( nT , t ) + X P ,( nT , t ) , t >  nT (7) dt ^{kk 1}

Let k be 1, the substituting equation (5) into in equation (7) results equation (8) considering ^E ( 1 0 , 1 0 ) = 0.

P 1 ( nT , t ) = X ( t - nT ) e ^X( t ^nT ) , t >  nT       (8)

We can compute P2 (nT, t), P3 (nT, t)l and so on through the method. Thus the probability P(nT, t) of k packets arriving over a period from the beginning of n-th

™ J                ™      ^{[ X ( nT} t ^{) ]} - x ( nT - 1 )

MAC frame and the current time t is            e , k!

Where X is the intensity, and t >  nT , k = 0,1,2, • • • , n = 0,1,2, l

The probability of traffic load based on the above computation is used for adjusting the cycles of wakeup and sleeping in time. The adaptive performance can reduce consume of energy and the delay resulting from excessive sleeping.

• D.    The FP-MAC protocol performance

Theorem 2. For V i , j , there exists t . <  t if p . is less than p_j .

Proof : According to the definition of t m = pT , we get the function as following.

t i - tj = PT2 - PT! = ^T 2 ( P. - Pj )

There exists p - p. > 0 due to the assumption and T2 > 0 , thus we get proof as below:

• t . <  t j

The theorem shows that the sensors with higher priority p_j have more slots to transmit data than sensors with lower priority p_i . This presents that FP-MAC protocol can provide a priority mechanism.

Theorem 3. For V i , j , p i , p _} , there exists t / t. = p / p .

j                    j

Proof. According to the definition of t m = p m T , we get proof as following:

t p T p — =---=--.

t j     p j T    p j

The theorem shows that the transmission slots t are proportional to its priority p for every group G . This presents that FP-MAC protocol can provide fairness for the sensors based on priority.

Theorem 4. FP-MAC protocol is a real-time MAC protocol.

Proof. FP-MAC protocol gives the slots assigning algorithm and the channel access algorithm. A packet of the sensor with priority p arrives at every time in the frame period. It cannot be sent immediately when having not priority to access the channel which results transmission delay. The maximum transmission delay is that a packet only can be sent at t of the next frame period belongs to itself when it arrives at the beginning of current frame for the sensor with the maximum ID number. The maximum transmission delay can be computed as following:

^D    = ^T + ⁽ t 1 + t 2 + L + t, )               ⁽⁹⁾

max( ID )

Similarly, the minimum transmission delay is that a packet only can be sent att of the current frame period belongs to itself when it arrives at the beginning of the frame for the sensor with the minimum ID number. The minimum transmission delay can be computed as following:

D = t + 1 + l + 1                 (10)

i .,.( ID )       ¹²              i ^{- 1}

The above analysis shows that FP-MAC protocol gives a bounded time delay and supports real-time traffic, thus it is a real-time MAC protocol.

• IV. Design of Improved Fair Priority MAC(IFP-MAC) Protocol

In many applications the data should be sent in the finite time. Such as in the networked control systems, the command should be sent to the controller in the time the system needed. Then the MAC protocol would support hard real-time data.

In the section we introduce a hard real-time fair multipriority MAC protocol. The hard real-time packets have the highest priority 0 and the other packets with different importance are prioritized into m levels from 1 to m. Higher levels mean higher priorities for transmission.

Like as the FP-MAC, IFP-MAC protocol also assigns transmission time according to its priority. For sensors with packets of the same priority, we will order these packets based on the sensor ID number. These sensors will send their packets according to the ID until all packets of the same priority are exhausted in the assigned transmission time. Then sensors with packets of the next priority level will join in transmission when last transmission time is over.

Let give the assumption of the Fair Multi-Priority MAC protocol.

Definition 5: The packets are prioritized into m levels which are respectively p ₀, p ₁, p ₂, L and p_m , in addition    p„ >  p, >  p, >  ... >  p . Without loss of

012    m

m generality, let ^ p. = 1.

i = 1

• A.    The IFP-MAC frame slots ass gn ng algor thm

The FP-MAC Protocol assumes a single, time-slotted channel for both data and broadcast message transmissions. Figure 1 shows the overall time-slot organization of the protocol. Time is organized as sections of random- and scheduled-access periods. We refer to random-access slots as broadcast slots and scheduled-access slots as data transmission slots. A frame time is set asT slots. The broadcast slots areT1 and data transmission slots are T . T is divided into t,t,tL t, 2  2             012 m and the sun oft,t,tLtisT . The Group M sensors can 012 m 2

transmit datum only in the t slots. m

• B.    The channel access algor thm

Sensors propagate one-hop neighbor information among neighboring nodes during the random access period using the broadcast slots. During the broadcast period, nodes perform contention based channel acquisition and thus signaling packets are prone to collisions. Sensors gather neighborhood information by exchanging broadcast packets during the random access period. The packets include the data priority and its own ID number. Figure 2 shows the format of the header of a broadcast packet. Sensor receives broadcast packets that carry neighborhood information and saves the neighborhood ID. After obtaining information the sensor in the same priority pm begins to compute the order Gmn in all sensors according to the ID number, such as the G sensor is the n-th sensor with the ID number from mn the minimum to the maximum in the group Gm . At the end of random access period all sensors get a unique order in its own priority group.

Considering the hard real-time packets with the priority p ₀ , let n is the number of the whole packets with priority p ₀ ,we set t_i as following:

After the ID initialization period, the sensors who already own IDs can enter the transmission period. These sensors will transmit their frames in a round-robin manner. The order that stations transmit can be in an ascending order of their ID numbers. At the beginning of t slots the minimum order sensor in the group G mm transmits packets first. Then the other sensors will transmit their frames in a round-robin manner. The order that sensors transmit can be in an ascending order of their G numbers. If t slots are out the sensor of the mn                    m current group must give the access chance to the sensor from next group. When the maximum order sensor of group Gm with the priority pm has finished transmitting the maximum order sensor will broadcast a beginning packet to the next group Gmif the t slots are still not out. The whole channel access algorithm is presented as following.

Algorithm 2. Pseudo-code description of channel access algorithm

• 1    initial priority level=m, T ;

• 2    compute the G for all sensors, t for group G . mn                     m                m

• 3    When level=0, let number of packets is n;

• 4    transmit packets in a round-robin manner from 1 to n;

• 5    For (priority level=1:m)

• 6    {IF (the sensor with minimum G receives mn

beginning broadcast from G m 1 OR t m begin;

• 7   {For ( G_mt =1:n)

• 8      { If ( t_m slots are not out)

• 9       { transmit data;

• 10    If (t=n AND G slots is less than t slots) mn                         m

• 11             { broadcast a beginning packet to

the G m + 1 };

• 12        }

• 13    }

• 14    }

• 15    }

• C.    The IFP-MAC protocol performance

Theorem 5. IFP-MAC protocol can provide a priority mechanism.

Proof : According to the definition of t0 = пт, we get the function that all the packets with priority p0 can be transmitted at first.

For p, < p, i, j * 0 , t, - tj = p, (T - t0) - pj(T -

= ^{( T} 2 — t 0 ) ( P , — P j )

There exists p. - p, > 0 due to the assumption and T2 -10 > 0 , thus we get proof as below: t , < tj.

The theorem shows that the sensors with higher priority p_j have more slots to transmit data than sensors with lower priority p_i . This presents that IFP-MAC protocol can provide a priority mechanism.

Theorem 6. IFP-MAC protocol is a hard real-time MAC protocol.

Proof. IFP-MAC protocol gives the slots assigning algorithm and the channel access algorithm. A packet of the sensor with priority p_i arrives at every time in the frame period. It cannot be sent immediately when having not priority to access the channel which results transmission delay. The packets with highest priority p 0 have п т time for transmitting. According to the assumption all the packets with priority p ₀ can be transmitted in the п т time, that is all the hard real-time packets can be guaranteed transmitting in time.

For the packets with priority p ,,, * 0, the maximum transmission delay is that a packet only can be sent atti of the next frame period belongs to itself when it arrives at the beginning of current frame for the sensor with the maximum ID number. The maximum transmission delay can be computed as following:

D = T ^{+ (} t о ⁺ t 1 ⁺ t 2 ⁺ L ⁺ t , )           ⁽¹³⁾

max( ID )

Similarly, the minimum transmission delay is that a packet only can be sent at t_i of the current frame period belongs to itself when it arrives at the beginning of the frame for the sensor with the minimum ID number. The minimum transmission delay can be computed as following:

D = L + t. + L + • l + 1 (14)

i -n( ID ) 0 12 I — 1

The above analysis shows that IFP-MAC protocol supports hard real-time traffic and gives bounded time delay, thus it is a hard real-time MAC protocol.

• V.    Simulation and experiment

• A.    Simulation results

This section evaluates the performance of our FP-MAC protocol on the NS2 platform and compares it with CSMA/CA, SMAC protocols. One thousand of sensors are deployed randomly in the area of l000m X l000m. The maximum communication range of a sensor is 80m. The likelihood of packets arriving over a period is modeled as a Poisson Process with intensity X . Let X be10 3 . The data rate is assumed to be 625 Kbps and frame size is 128 bytes. The period T is set as 300ms and a slot is set as 2ms. The priority p ₁, p ₂, p ₃ is set as 0.6 ， 0.3 and 0.1 respectively.

Figure 3 shows the average delays for different priority under our MAC protocol. The data with higher priority do present much shorter delays than the data with lower priority. Note that only data that are successfully transmitted are counted in this measurement. When the load is very heavy, the average delay with lower priority rapidly increases first. While the change rates of average delays for different priority become stable because of fairness performance of the MAC. Figure 4 compares the average delay of our MAC protocol against CSMA/CA and SMAC protocols under different traffic loads. The figure shows that FP-MAC protocol can provide the bounded delay. Networks can adjust the average delay by modifying the frame period T . The average delay decreases when T becomes smaller.

the packets generation rate(frame/ms)

Figure 3. Average delays with different priority

Figure 5 shows the relationship between throughput and traffic load. As seen from Figure 4 FP-MAC provides a higher throughput than SMAC protocol. There exists a difference on the throughput with different priority. The throughput is higher with higher priority and it becomes a constant when traffic load arrives at a threshold. This also presents that FP-MAC supports real time communication based on priority.

Figure 4. Comparison of average delay under different traffic loads

Figure 5. Network throughput under different traffic loads

Figure 6. Data loss probability under different traffic load

Figure 6 and Figure 7 show the data loss probabilities against the traffic load. The data loss probabilities of CSMA and SMAC protocols increase rapidly with the increasing traffic load because of collision. FP-MAC protocol shows good performance due to its slots assigning algorithm. The data loss probability with higher priority is much less than data with lower priority because of more slots assigned. The hard real-time packets have zero loss probabilities in the IFP-MAC protocol. Therefore, our protocol is very suitable for transmitting real time traffic.

Figure 7. Data loss probability under different traffic load

• B.    Experiment

  In the experiment sensor node named NU-NODE is designed. Typical choices for the microcontroller are the 8 bit Atmel ATmega128. A low-power, single-chip, IEEE 802.15.4 compliant wireless radio is adopted in the wireless sensor design. The newly created IEEE 802.15.4 standard is especially suitable for distributed computation, as it was developed for true ad-hoc and wireless sensor networks among battery powered wireless devices. For the wireless communication system, the chipcon CC2420 is selected. The power is supported by the mobile phone battery. NU-NODE node is shown in Figure 8. Tinyos2.x developed by UC Berkeley is used on NU-NODE node.

Figure 8. NU-NODE

As shown in Figure 9 the topology is setup. We measure the time from MAC to MAC between sensors. The measure method is that a sensor transmits a packet to the receiver and the receiver returns the packet immediately. Now we can read the time stamp on the two sensor nodes and compute the time from MAC to MAC. First we make experiment under CSMA/CD MAC protocol. The time from MAC to MAC is approximately 0.195ms under different traffic load.

Figure 9. sensor node topology for the experiment

FP-MAC protocol runs on the same experiment setup. The priority p ₁, p ₂, p ₃ is set as 0.6 ， 0.3 and 0.1 respectively. The result shows that the time from MAC to MAC is 0.136ms with priority 0.6 using the same measure method. This presents that FP-MAC protocol supports real time communication based on priority.

• VI.    Conclusions

Most of WSNs applications require real-time traffic. This paper presents a medium access control protocol that provides multiple priority levels. The channel is accessed by sensors according to their priorities. For sensors with the same priority, they send frames in a round manner. In addition the fairness between different priorities is guaranteed. Simulation and experiment results indicate that FP-MAC protocol provides high channel utilization and bounded delays for real-time communication and can be well adapted in dynamic wireless sensor networks.