# The Lyapunov Optimization for Two-Tier Hierarchical-Based MAC in Cloud Robotics

Authors: Yansu Hu; Ang Gao; Changqing Wang; Wen Cao; Maode Yan
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Cloud robotics can largely enhance the robot intelligence by offloading tasks to the cloud dynamically. However, the robots differ in their own hardware configuration such as battery and processing capacity, while the transmission frames are also a mixture of different quality of service (QoS) requirements. As the competition for limited channel resource is inevitable, how to optimize the system performance by effective resource allocation is a key problem. The paper proposes a two-tier hierarchical-based MAC (Two-Tier MAC) which means the classification exists not only in frames but also in robots. The Lyapunov optimization technique is used to maximize the time-averaged quality satisfaction. The experiments show the superior performance of the Two-Tier MAC compared with other MAC protocols especially in overloaded networks. Meanwhile, the system also presents a longer lifetime because the Two-Tier MAC takes energy balance into consideration.


---

## Body

## 1. Introduction

Robotics is evolving from a single platform to cluster collaboration for the applications with high complexity, uncertainty, and real time. Although robots share information and cooperate with each other by a decentralized wireless network, the intelligence is still limited by their own hardware configuration. Cloud robotics [1] provides a novel concept to break the individual limitation in low intelligence and processing capacity. By means of the offloading task to cloud dynamically, robots get rid of the huge storage and intensive computing bottleneck.As shown in Figure1, the offloading task is divided into a series of flows and is processed on cloud hosts in parallel by virtualization technology. Task flows are then repacked by upper layers with header information and finally encapsulated into MAC frames in the data link. For enhancing the survival ability in complex environment, robots adopt a decentralized ad hoc network and contend for communication channel in the carrier sense multiple access/collision avoidance (CSMA/CA) mode.Figure 1
Two-Tier MAC architecture of cloud robotics.As the competition is inevitable, how to allocate the limited resource to guarantee the QoS performance and maximize the total system utility is a big challenge for the offloading scenario. Frame differentiation is easily thought of. For example, simultaneous localization and mapping (SLAM) should enjoy a better real-time than environment monitoring application. However, robots themselves also differ in processing capacity, hardware configuration, task emergency, and so on which is often overlooked. Meanwhile, the network condition is time varying which is hard to predict. When the network is overloading, the system cannot support the QoS for all robots. The data arrival rate should be adjusted to avoid blocking.For the problems above, the paper proposes a two-tier hierarchical-based MAC (Two-Tier MAC) to realize the classification on both frames and robots. The Lyapunov optimization technique as well as isolated time slots and admission control is adopted to maximize the system utility even in poor network condition. The main contributions are as follows:(i)
The classification on both frames and robots is considered. All frames are divided into different priorities waiting in corresponding queues with isolated time slots to reduce collision consumption. Frames in the same queue but from different robots are allocated diverse accessing probability to ensure the energy balance(ii)
The system optimization can be decoupled into two independent issues by the Lyapunov method. One is admission control (AC) in which the frames will be rejected when the network is overloading. The other is resource allocation (RA) to adjust the accessing probability to maximize the system utility functionThe rest of the paper is organized as follows. Chapter II reviews related works. In Chapter III, the scheme of the Two-Tier MAC is detailed. The Lyapunov optimization method is described in Chapter IV. In Chapter V, a series of experiments are operated to test the effectiveness of the Two-Tier MAC. The conclusion and future work are illustrated in Chapter VI.


## 2. Related Works

Since the widespread of heterogeneous, crosslayered “thin robots,” it is the best way to control the network transmission in the MAC layer or transceivers in the physics layer.Some researches based on multiqueuing architecture have realized QoS support by assigning different queues with different resource or CSMA/CA parameters, such as contention window size, interframe space, active time, transmission power, TCP congestion window, and data rate [2, 3]. In specific, QoS-based MAC [2] adjusts the contention window for diverse QoS requirements and duty cycle to preserve sensory energy. PRIN-MAC [4] can minimize energy consumption and increase system throughput by varying the interarrival time according to the packets priorities. ASMAC [5] avoids overhearing and reduces contention and delay by asynchronously scheduling the wake-up time of neighboring nodes. RF-MAC [6] focuses on how the placement, chosen frequency, and number of RF energy transmitters impact the sensor charging time. CACC-MAC [7] is proposed for crosslayer congestion control by the dynamic TCP congestion window and MAC contention window scheme. The mechanism proposed in [3] operates QoS provisioning at the MAC layer for urgent traffic and provides data rate adjustment at the application layer. Each algorithm can improve QoS performance in certain scenarios. However, they are verified from the view of system realization or protocol design without theory analysis such as system stability and dynamic performance.Based on this problem, we have tried to apply control theory in this area in recent years. FD-MAC [8] designs a less-step controller to provide proportional delay differentiated (PDD) QoS support. It adopts a linear model for system identification which is not precisely enough and without taking energy consumption into consideration. On this basis, CSFD-MAC [9] proposes a cascade self-tuning architecture as well as active power management, and MQEB-MAC [10] adopts a back propagating (BP) neural network to develop an all-in-one mixed QoS insurance and energy-balanced scheme. Although the algorithms above are verified to be valid by experiments, they still have the following limitations: Firstly, they only focus on the difference in frames but neglect the heterogeneity of the robots themselves. Secondly, channel condition is time varying, but few papers notice the system performance under poor channel conditions which is actually a common scenario in the wireless network. Thirdly, the mathematical model above is either too simple such as the linear system or low in real time such as the BP neural network.


## 3. System Model

### 3.1. Two-Tier Hierarchical Architecture

Figure1 shows the Two-Tier MAC architecture for cloud robotics, and Table 1 exhibits all the variables present in the paper. There are M robots, and all frames are divided into N types waiting in the isolated queues without interference. Note that blocks with the same color come from the same robot, while blocks fulfilled with the same shape have the same frame priority.Table 1
Nomenclature.
M
Number of robots
N
Number of frame types
CW
Size of contention window
ρ
m
,
n
Accessing probability ofnth frame type in robot m
S
Total number of time slots in a duty-cycling
s
n
Number of time slots allocated tonth frame
λ
n
t
Arrival rate fornth queue
R
n
t
Admission rate fornth queue
w
n
Positive weightnth queue
u
n
t
Utility function fornth queue
μ
n
t
Service rate fornth queue
Q
n
t
Data backlog fornth queue
v
m
PHY transmission ratio formth robot
τ
m
Class factor formth robot
E
.
Mathematical expectation
Γ
Fitness function
s
n
′
Normalized value ofsn
I
binary
Binary chromosome vector
F
code
Coding function
F
decode
Decoding functionTo avoid blocking, the arrival rate should be adjusted according to the channel condition. For example, if one queue is fulfilled, the robot should reject new corresponding arrived frames. Queues will be allocated different time slots according to the frame priority, and frames in the same queue are allocated diverse accessing probability according to robot classification.


### 3.2. Time Slot Isolation

Actually, the robots are power driven related to system lifetime. Isolated time slots are adopted to reduce the collision energy consumption. Frames contend for communication channel by the CSMA/CA mode, with the key algorithm that once the collision is detected, the node will wait for a random back off in the range of0,CWCWmin≤CW≤CWmax where CW is called the contention window. The more intensive a robot attempts to transmit frames, the higher the probability collision and retransmission occur, which will not only cause the unnecessary energy wasting but also induce a large end-to-end delay. Define ρ to be the accessing probability, then(1)ρ=2CW+1.Figure1 also shows a dynamic time slot isolation framework. There are S time slots in total, and sn means the number of time slots allocated to the nth queue (∑sn≤S,n=1,2,⋯N). Frames with the same priority content for channel medium in specified time slots are actually a kind of resource reservation mechanism to avoid the across-class contention. Data arrival rate of robots is independently and identically distributed (i.i.d). Without loss of generality, assume the data priority is prefixed or dynamically negotiated by high level protocol, and robots are classified by battery capacity.


### 3.3. Utility Function

In thenth queue, suppose that the arrival rate and the admission rate are λnt and Rnt, respectively. Although each frame expects a higher admission rate, it is still limited by data arrival rate, i.e.,(2)0≤Rnt≤λnt,∀n,t.It is known that user experience and satisfaction follow logarithmic laws [11]. Since the normalized positive weight vector w1,w2,⋯wnT0≤wn≤1,∑wn=1 is prefixed by a high level protocol, the utility function for the nth queue can be written as(3)unt=wnlog2Rnt,n=1,2,⋯N.


### 3.4. Queuing Model

DefineQnt to be the data backlog (number of frames waiting in the queue) for the nth queue at time t. The queue grows with the admission rate Rnt and gets short with the service rate μnt. According to the queue theory [12], the recursive formula of queue length is(4)Qnt+1=maxQnt−μnt,0+Rnt.As mentioned before, frames are with the same priority content for the channel medium in specified time slots in the manner of CSMA/CA. So the service rate mainly depends on both the time slots and accessing probability. For every robot, supposing PHY transmission ratio isvmn=1,2,⋯M, the class factor is τm, then the service rate is(5)μnt=τmvmρmnsnS,where ρmn is the accessing probability of the nth frame type in robot m. So there is(6)0≤ρmn≤1,∑n=1Nρmn=1,∀m.According to paper [13], an individual queue Qnt is the mean-rate-stable if(7)limT→∞EQntT=0,and a network is stable if all individual queues in the network are stable. In a real system, the mean rate stability implies that the long-term average departure rate from the queue is greater than or equal to the long-term average input rate injected into the queue, i.e., limT→∞1/T∑t=0T−1μnt≥limT→∞1/T∑t=0T−1Rnt. Thus, all frames placed in the queue will be finally transmitted when the data queue is mean-rate-stable.


### 3.5. Problem Formulation

In summary, the utility function can be optimized by adjusting the time slotssn and accessing the probability ρmn dynamically. The problem can be described as(8)P1:maxRt,st,ρtlimT→∞1T∑t=1T−1E∑n=1Nunt,s.t.(C1)0≤Rnt≤λn,∀n,t,(C2)0≤ρmnt≤1,∑n=1Nρmnt=1,∀m,(C3)0≤snt≤S,∑n=1Nsnt≤S,(C4)limT→∞EQntT=0,where Rt=Rnt, st=snt, and ρt=ρmnt are the optimized parameter vector/matrix to be solved. C1 constrains the admission rate which cannot exceed the arrival rate. C2 constrains the accessing probability which is in the range of [0,1], and the total value of different frame priorities in one robot at a time should equal to 1. C3 constrains the time slots which are limited by an upper bound for energy consumption, and C4 constrains the queue which is mean-rate-stable.


## 3.1. Two-Tier Hierarchical Architecture

Figure1 shows the Two-Tier MAC architecture for cloud robotics, and Table 1 exhibits all the variables present in the paper. There are M robots, and all frames are divided into N types waiting in the isolated queues without interference. Note that blocks with the same color come from the same robot, while blocks fulfilled with the same shape have the same frame priority.Table 1
Nomenclature.
M
Number of robots
N
Number of frame types
CW
Size of contention window
ρ
m
,
n
Accessing probability ofnth frame type in robot m
S
Total number of time slots in a duty-cycling
s
n
Number of time slots allocated tonth frame
λ
n
t
Arrival rate fornth queue
R
n
t
Admission rate fornth queue
w
n
Positive weightnth queue
u
n
t
Utility function fornth queue
μ
n
t
Service rate fornth queue
Q
n
t
Data backlog fornth queue
v
m
PHY transmission ratio formth robot
τ
m
Class factor formth robot
E
.
Mathematical expectation
Γ
Fitness function
s
n
′
Normalized value ofsn
I
binary
Binary chromosome vector
F
code
Coding function
F
decode
Decoding functionTo avoid blocking, the arrival rate should be adjusted according to the channel condition. For example, if one queue is fulfilled, the robot should reject new corresponding arrived frames. Queues will be allocated different time slots according to the frame priority, and frames in the same queue are allocated diverse accessing probability according to robot classification.


## 3.2. Time Slot Isolation

Actually, the robots are power driven related to system lifetime. Isolated time slots are adopted to reduce the collision energy consumption. Frames contend for communication channel by the CSMA/CA mode, with the key algorithm that once the collision is detected, the node will wait for a random back off in the range of0,CWCWmin≤CW≤CWmax where CW is called the contention window. The more intensive a robot attempts to transmit frames, the higher the probability collision and retransmission occur, which will not only cause the unnecessary energy wasting but also induce a large end-to-end delay. Define ρ to be the accessing probability, then(1)ρ=2CW+1.Figure1 also shows a dynamic time slot isolation framework. There are S time slots in total, and sn means the number of time slots allocated to the nth queue (∑sn≤S,n=1,2,⋯N). Frames with the same priority content for channel medium in specified time slots are actually a kind of resource reservation mechanism to avoid the across-class contention. Data arrival rate of robots is independently and identically distributed (i.i.d). Without loss of generality, assume the data priority is prefixed or dynamically negotiated by high level protocol, and robots are classified by battery capacity.


## 3.3. Utility Function

In thenth queue, suppose that the arrival rate and the admission rate are λnt and Rnt, respectively. Although each frame expects a higher admission rate, it is still limited by data arrival rate, i.e.,(2)0≤Rnt≤λnt,∀n,t.It is known that user experience and satisfaction follow logarithmic laws [11]. Since the normalized positive weight vector w1,w2,⋯wnT0≤wn≤1,∑wn=1 is prefixed by a high level protocol, the utility function for the nth queue can be written as(3)unt=wnlog2Rnt,n=1,2,⋯N.


## 3.4. Queuing Model

DefineQnt to be the data backlog (number of frames waiting in the queue) for the nth queue at time t. The queue grows with the admission rate Rnt and gets short with the service rate μnt. According to the queue theory [12], the recursive formula of queue length is(4)Qnt+1=maxQnt−μnt,0+Rnt.As mentioned before, frames are with the same priority content for the channel medium in specified time slots in the manner of CSMA/CA. So the service rate mainly depends on both the time slots and accessing probability. For every robot, supposing PHY transmission ratio isvmn=1,2,⋯M, the class factor is τm, then the service rate is(5)μnt=τmvmρmnsnS,where ρmn is the accessing probability of the nth frame type in robot m. So there is(6)0≤ρmn≤1,∑n=1Nρmn=1,∀m.According to paper [13], an individual queue Qnt is the mean-rate-stable if(7)limT→∞EQntT=0,and a network is stable if all individual queues in the network are stable. In a real system, the mean rate stability implies that the long-term average departure rate from the queue is greater than or equal to the long-term average input rate injected into the queue, i.e., limT→∞1/T∑t=0T−1μnt≥limT→∞1/T∑t=0T−1Rnt. Thus, all frames placed in the queue will be finally transmitted when the data queue is mean-rate-stable.


## 3.5. Problem Formulation

In summary, the utility function can be optimized by adjusting the time slotssn and accessing the probability ρmn dynamically. The problem can be described as(8)P1:maxRt,st,ρtlimT→∞1T∑t=1T−1E∑n=1Nunt,s.t.(C1)0≤Rnt≤λn,∀n,t,(C2)0≤ρmnt≤1,∑n=1Nρmnt=1,∀m,(C3)0≤snt≤S,∑n=1Nsnt≤S,(C4)limT→∞EQntT=0,where Rt=Rnt, st=snt, and ρt=ρmnt are the optimized parameter vector/matrix to be solved. C1 constrains the admission rate which cannot exceed the arrival rate. C2 constrains the accessing probability which is in the range of [0,1], and the total value of different frame priorities in one robot at a time should equal to 1. C3 constrains the time slots which are limited by an upper bound for energy consumption, and C4 constrains the queue which is mean-rate-stable.


## 4. Lyapunov Optimization

### 4.1. Problem Transformation

The queue system should be stable, so the Lyapunov method is used to ensure the stability in the long term. Define the Lyapunov function as(9)LGt=12∑n=1NQn2t.Without loss of generality, assume all queues are empty whent=0, i.e., LG0=0. Lyapunov function drift is(10)ΔLt≜ΞLGt+1−LGt.The drift-minus-reward term has an upper bound according to Lemma1.Lemma 1 (see [14]).
For any nonnegative real numberQ, b, and a, there holds that(11)maxQ−b,0+A2≤Q2+b2+A2+2QA−b,(12)ΔLt−V∑n=1Nunt≤B+E∑n=1NQntRnt−μnt=B+E∑n=1NQntRnt−Vwnlog2Rnt−E∑n=1NQntμnt,where B=E∑n=1NRn2t+μn2t/2 is defined as a finite constant to simplify the inequation above, and V is a nonnegative constant parameter that controls the trade-off between drift ΔLt and satisfaction function. By the Lyapunov optimization technique, problem P1 can be transformed into minimizing the right-hand side (RHS) of (12) subjected to constraints C1-C4.Furthermore, according to Equation (12), P1 can be decoupled into two subproblems: the first one is the admission control (AC) related to Rt, which means the new frames will be rejected if the queue is full. The second one is the resource allocation (RA) related to st and ρt to guarantee the higher priority could enjoy a better QoS performance.


### 4.2. Admission Control

Due to the resource limitation, admission control is adopted to ensure that the QoS performance will not degrade below an acceptable level even in the overloading case. Based on Equation (12), the AC problem is formulated as(13)P2:minRnt∑n=1NQntRnt−Vwnlog2Rnt,s.t.(14)0≤Rnt≤λn,∀n,t.Easily verify that P2 is a convex optimization problem. Set the derivative ofQntRnt−Vwnlog2Rnt with respect to Rnt to be 0 to solve the service rate:(15)Qnt−VwnRntln2=0,Rnt=VwnQntln2=0.Since the admission rate is also limited by arrival rate, the optimal AC decision is(16)Rn∗t=minVwnQntln2,λn.


### 4.3. Resource Allocation

For the RA problem, both the time slots and accessing probability should be optimized to maximize P3:(17)P3:maxsnt,ρmntE∑n=1NQntvmρmnsnS,s.t.(18)0≤ρmnt≤1,∑n=1Nρmnt=1,∀m,(19)0≤snt≤S,∑n=1Nsnt≤S.P3 is nonconvex and may have several local minima, which make it different to find the closed-form solution. In recent years, some heuristic algorithms have been applied and proven to be valid. In this paper, the genetic algorithm (GA) as shown in Algorithm1 is used for it can jump out of local minimal points and obtain the global optimization by finding a better artificial population iteratively.Algorithm 1: GA algorithm.
Input: size of the population T, maximum generation G, crossover probability pc, mutation probability pm.
Output:argmaxρ,s′Γ.
1Initialization
2 Randomly initialize setsT of optimization’s variables ρ,s′tt=1,⋯T as the initial population with constrains C2 and C3’
3 Codingρ,s′t into Ibinary by function Fcode, i.e., Ig=1=I1binary,⋯ITbinary
4Whileg≤Gdo
5 Calculate the individual fitnessΓtg according Fdecode
6 Calculate the selection probabilityptg=Γtg/∑tTΓig
7 Save the best fitnessΓ∗g and the corresponding individual I∗binary
8IfΓ∗g−Γ∗g−1≤δ, then
9ReturnFdecodeI∗binary
10End
11Selection: randomly choose T chromosomes as a new population by Roulette Wheel selection
12Crossover: for every two pair of individuals in I∧g, take multi-point crossover at every gene position with probability pc
13Mutation: for every individual in I∧g, take binary-reverse at every gene position with the probability pm
14Ig←I∧g∩I∗binary
15g=g+1
16End
17ReturnFdecodeI∗binaryFor the unified value range of variables, takesn′=sn/S to replace original sn:(C3’)0≤sn′≤1,0≤∑sn′≤1.The fitness function is denoted asΓ=E∑n=1NQntvmρmnsn′. Since ρ∈RM×N, s′∈RN are interpreted into a binary chromosome by a 16-bit Gray code, each individual can be represented by a 16MN+16N-bit-long binary vector, i.e., Ibinary=ρ16×M×Nbinary,s′16×Nbinary. The coding and decoding functions used in Algorithm 1 are defined as Ibinary=Fcodeρ,s′ and ρ,s′=FdecodeIbinary, respectively. The superscript g denotes the number of generations. The output of GA is ρ,s′, and ρ can be adjusted by CW according to Equation (1).Since P3 is nonconvex, it is hard to prove the convergence in a mathematical way. However, as shown in Figure2, the GA algorithm can converge with a finite number of generations by simulation with different crossover probability pc and mutation probability pm.Figure 2
Convergence of GA with differentpc and pm.


## 4.1. Problem Transformation

The queue system should be stable, so the Lyapunov method is used to ensure the stability in the long term. Define the Lyapunov function as(9)LGt=12∑n=1NQn2t.Without loss of generality, assume all queues are empty whent=0, i.e., LG0=0. Lyapunov function drift is(10)ΔLt≜ΞLGt+1−LGt.The drift-minus-reward term has an upper bound according to Lemma1.Lemma 1 (see [14]).
For any nonnegative real numberQ, b, and a, there holds that(11)maxQ−b,0+A2≤Q2+b2+A2+2QA−b,(12)ΔLt−V∑n=1Nunt≤B+E∑n=1NQntRnt−μnt=B+E∑n=1NQntRnt−Vwnlog2Rnt−E∑n=1NQntμnt,where B=E∑n=1NRn2t+μn2t/2 is defined as a finite constant to simplify the inequation above, and V is a nonnegative constant parameter that controls the trade-off between drift ΔLt and satisfaction function. By the Lyapunov optimization technique, problem P1 can be transformed into minimizing the right-hand side (RHS) of (12) subjected to constraints C1-C4.Furthermore, according to Equation (12), P1 can be decoupled into two subproblems: the first one is the admission control (AC) related to Rt, which means the new frames will be rejected if the queue is full. The second one is the resource allocation (RA) related to st and ρt to guarantee the higher priority could enjoy a better QoS performance.


## 4.2. Admission Control

Due to the resource limitation, admission control is adopted to ensure that the QoS performance will not degrade below an acceptable level even in the overloading case. Based on Equation (12), the AC problem is formulated as(13)P2:minRnt∑n=1NQntRnt−Vwnlog2Rnt,s.t.(14)0≤Rnt≤λn,∀n,t.Easily verify that P2 is a convex optimization problem. Set the derivative ofQntRnt−Vwnlog2Rnt with respect to Rnt to be 0 to solve the service rate:(15)Qnt−VwnRntln2=0,Rnt=VwnQntln2=0.Since the admission rate is also limited by arrival rate, the optimal AC decision is(16)Rn∗t=minVwnQntln2,λn.


## 4.3. Resource Allocation

For the RA problem, both the time slots and accessing probability should be optimized to maximize P3:(17)P3:maxsnt,ρmntE∑n=1NQntvmρmnsnS,s.t.(18)0≤ρmnt≤1,∑n=1Nρmnt=1,∀m,(19)0≤snt≤S,∑n=1Nsnt≤S.P3 is nonconvex and may have several local minima, which make it different to find the closed-form solution. In recent years, some heuristic algorithms have been applied and proven to be valid. In this paper, the genetic algorithm (GA) as shown in Algorithm1 is used for it can jump out of local minimal points and obtain the global optimization by finding a better artificial population iteratively.Algorithm 1: GA algorithm.
Input: size of the population T, maximum generation G, crossover probability pc, mutation probability pm.
Output:argmaxρ,s′Γ.
1Initialization
2 Randomly initialize setsT of optimization’s variables ρ,s′tt=1,⋯T as the initial population with constrains C2 and C3’
3 Codingρ,s′t into Ibinary by function Fcode, i.e., Ig=1=I1binary,⋯ITbinary
4Whileg≤Gdo
5 Calculate the individual fitnessΓtg according Fdecode
6 Calculate the selection probabilityptg=Γtg/∑tTΓig
7 Save the best fitnessΓ∗g and the corresponding individual I∗binary
8IfΓ∗g−Γ∗g−1≤δ, then
9ReturnFdecodeI∗binary
10End
11Selection: randomly choose T chromosomes as a new population by Roulette Wheel selection
12Crossover: for every two pair of individuals in I∧g, take multi-point crossover at every gene position with probability pc
13Mutation: for every individual in I∧g, take binary-reverse at every gene position with the probability pm
14Ig←I∧g∩I∗binary
15g=g+1
16End
17ReturnFdecodeI∗binaryFor the unified value range of variables, takesn′=sn/S to replace original sn:(C3’)0≤sn′≤1,0≤∑sn′≤1.The fitness function is denoted asΓ=E∑n=1NQntvmρmnsn′. Since ρ∈RM×N, s′∈RN are interpreted into a binary chromosome by a 16-bit Gray code, each individual can be represented by a 16MN+16N-bit-long binary vector, i.e., Ibinary=ρ16×M×Nbinary,s′16×Nbinary. The coding and decoding functions used in Algorithm 1 are defined as Ibinary=Fcodeρ,s′ and ρ,s′=FdecodeIbinary, respectively. The superscript g denotes the number of generations. The output of GA is ρ,s′, and ρ can be adjusted by CW according to Equation (1).Since P3 is nonconvex, it is hard to prove the convergence in a mathematical way. However, as shown in Figure2, the GA algorithm can converge with a finite number of generations by simulation with different crossover probability pc and mutation probability pm.Figure 2
Convergence of GA with differentpc and pm.


## 5. Experiments and Results

The experiments are operated by ZigBit TM 900 hardware module with Atmel R AVR2025 software package. Specifically, ZigBit TM 900 is a 784/868/915 MHz IEEE 802.15.4 OEM module, while AVR2025 is a configurable MAC stack for ZigBit 900, which provides the fundamental abstract methods for hardware operation and a secondary development supported the MAC stack.30 robots classified into 3 groups according to their battery configuration are deployed in the radius of 100 m. Every node randomly sends data packets to the other. Packets are encapsulated into MAC frames with 3 different priorities which are preset by upper layers asω1:w2:w3=3:2:1. A larger value means a better service.The interval of frames obeys the normal distribution with the average of−T¯t/log1−K, where K0<K<1 is the offered traffic normalized by service data rate. The frame length follows the Pareto distribution with the shape parameter of 1.1 and average of 105×8 bits. The transmitted power is 1 mW, CWmin=23, CWmax=28. The average frame length is 105 bytes and the symbol rate is 256 kbps.


### 5.1. Static Performance

Static performance concerns the throughput, power consumption, and energy efficiency changing with time, which are related to system utility, lifetime, and data transmission efficiency, respectively. Energy efficiency is defines as(20)Eff=∑lenienergy=∑leni/tenergy/t=ΞlenN/tpower=Ξlenthroughputpower.The experiments last 800 s, and 4 different MAC protocols (IEEE 802.15.4, FD-MAC, MQEB-MAC, and Two-Tier MAC) are compared.(1)
During 0-200 s, it runs the original IEEE 802.15.4 MAC without any classification scheme(2)
During 200-400 s, FD-MAC operates for frame differentiation. However, the throughput remains nearly the same, and the presented energy efficiency drops slightly. That is because in channel contention, energy is consumed once a node transmits whether or not the data is correctly received. FDMAC which makes a small CW size with high priority increases the collision probability, which will induce unwanted re-transmission and energy wasting(3)
During 400-600 s, MQEB-MAC presents its advance in both throughput and energy efficiency because of the time slot isolation and BP self-tuning control. However, energy saving by only reducing the time slots allocated to soft QoS traffic limits further performance improvement(4)
During 600-800 s, Two-Tier MAC takes over to maximize the system utility. Throughput is increased because of Lyapunov optimization, and the power consumption is reduced because of the time slot isolation scheme for avoiding across-class collision. As a result, the energy efficiency is largely improved compared with the other three MAC protocols, specifically, about 50.1%, 55.4%, and 23.8% enhancement compared with IEEE 802.15.4, FD-MAC, and MQEBMAC, respectivelyNotice that for a specific MAC protocol, frames with high priority enjoy a large throughput but at the same time will lead to more power consumption. So no matter which frame priority, there is no big difference in energy efficiency of the same protocol (Figure3(c)). The phenomenon will also be present in Section 5.2.Figure 3
Static performance along with time.
(a)
Throughput
(b)
Power
(c)
Energy efficiency


### 5.2. Statistic Performance

Figure4 shows the statistic performance of the Two-Tier MAC on each robot. 30 robots are classified into 3 groups according to their battery configuration as shown in Table 2, and the factor is τ1:τ2:τ3=4:3:2.Figure 4
Statistic performance of Two-Tier MAC.
(a)
Throughput
(b)
Power
(c)
Energy efficiencyTable 2
Battery configuration.
Classification
Robot number
Battery configuration
Class 1
No.01-no.10
2000 mAh/3.7 V
Class 2
No.11-no.20
1800 mAh/3.7 V
Class 3
No.21-no.30
1500 mAh/3.7 VFor one robot itself, the frames with different priorities are distinguished. Frames with a higher priority enjoy a better throughput which is in accordance with the results shown in Figure3.Among different robots, the ones in the higher class still have a better throughput statistically (Figure3(a)) but lead to more power consumption (Figure 3(b)). As a result, no matter which frame priority or robot class, the energy efficiency is always approximately equal (Figure 3(c)). This conclusion is greatly meaningful to the system lifetime discussed below.Define the system lifetime as the moment when the first robot is out of battery. The lifetime in different protocols is shown in Table3. Obviously, the lifetime in the Two-Tier MAC will be extended to take energy balance into consideration.Table 3
System lifetime in different MAC protocols.
MAC protocols
Lifetime (min)
IEEE 802.15.4
102
FD-MAC
96
MQEB-MAC
109
Two-Tier MAC
117


### 5.3. Dynamic Performance

The experiments above only consider the normal load scene. However, traffic burst is more common in cloud robotics. Here, we focus on the effect of varying arrival rates to the system performance, i.e., dynamic performance, especially in the overloading situation. The parameter setting is the same as the former except that the arrival rate changes in the range of 50-350 frame/s.As shown in Figure5, when the system capacity is unsaturated (50-250 frame/s), the throughput is proportional to the growth of the arrival rate for all protocols. The features of power consumption and energy efficiency present similar characteristic with Section 5.1. After that, robots suffer from traffic bursting which leads to distinct performance in the four protocols.Figure 5
Dynamic performance along with arrival rate.
(a)
Throughput
(b)
Power
(c)
Energy efficiencyFor 802.15.4, FD-MAC, and MQEB-MAC, network congestion occurs, and the system performance is reduced because of the noncongesting protection mechanism. Data loss will consume extra energy and lead to the degradation of throughput and energy efficiency. On the contrary, thanks to the admission control, the Two-Tier MAC could reject new frames when the network is overloading to avoid network congestion. So the energy efficiency can be maintained even in this severe network environment.


## 5.1. Static Performance

Static performance concerns the throughput, power consumption, and energy efficiency changing with time, which are related to system utility, lifetime, and data transmission efficiency, respectively. Energy efficiency is defines as(20)Eff=∑lenienergy=∑leni/tenergy/t=ΞlenN/tpower=Ξlenthroughputpower.The experiments last 800 s, and 4 different MAC protocols (IEEE 802.15.4, FD-MAC, MQEB-MAC, and Two-Tier MAC) are compared.(1)
During 0-200 s, it runs the original IEEE 802.15.4 MAC without any classification scheme(2)
During 200-400 s, FD-MAC operates for frame differentiation. However, the throughput remains nearly the same, and the presented energy efficiency drops slightly. That is because in channel contention, energy is consumed once a node transmits whether or not the data is correctly received. FDMAC which makes a small CW size with high priority increases the collision probability, which will induce unwanted re-transmission and energy wasting(3)
During 400-600 s, MQEB-MAC presents its advance in both throughput and energy efficiency because of the time slot isolation and BP self-tuning control. However, energy saving by only reducing the time slots allocated to soft QoS traffic limits further performance improvement(4)
During 600-800 s, Two-Tier MAC takes over to maximize the system utility. Throughput is increased because of Lyapunov optimization, and the power consumption is reduced because of the time slot isolation scheme for avoiding across-class collision. As a result, the energy efficiency is largely improved compared with the other three MAC protocols, specifically, about 50.1%, 55.4%, and 23.8% enhancement compared with IEEE 802.15.4, FD-MAC, and MQEBMAC, respectivelyNotice that for a specific MAC protocol, frames with high priority enjoy a large throughput but at the same time will lead to more power consumption. So no matter which frame priority, there is no big difference in energy efficiency of the same protocol (Figure3(c)). The phenomenon will also be present in Section 5.2.Figure 3
Static performance along with time.
(a)
Throughput
(b)
Power
(c)
Energy efficiency


## 5.2. Statistic Performance

Figure4 shows the statistic performance of the Two-Tier MAC on each robot. 30 robots are classified into 3 groups according to their battery configuration as shown in Table 2, and the factor is τ1:τ2:τ3=4:3:2.Figure 4
Statistic performance of Two-Tier MAC.
(a)
Throughput
(b)
Power
(c)
Energy efficiencyTable 2
Battery configuration.
Classification
Robot number
Battery configuration
Class 1
No.01-no.10
2000 mAh/3.7 V
Class 2
No.11-no.20
1800 mAh/3.7 V
Class 3
No.21-no.30
1500 mAh/3.7 VFor one robot itself, the frames with different priorities are distinguished. Frames with a higher priority enjoy a better throughput which is in accordance with the results shown in Figure3.Among different robots, the ones in the higher class still have a better throughput statistically (Figure3(a)) but lead to more power consumption (Figure 3(b)). As a result, no matter which frame priority or robot class, the energy efficiency is always approximately equal (Figure 3(c)). This conclusion is greatly meaningful to the system lifetime discussed below.Define the system lifetime as the moment when the first robot is out of battery. The lifetime in different protocols is shown in Table3. Obviously, the lifetime in the Two-Tier MAC will be extended to take energy balance into consideration.Table 3
System lifetime in different MAC protocols.
MAC protocols
Lifetime (min)
IEEE 802.15.4
102
FD-MAC
96
MQEB-MAC
109
Two-Tier MAC
117


## 5.3. Dynamic Performance

The experiments above only consider the normal load scene. However, traffic burst is more common in cloud robotics. Here, we focus on the effect of varying arrival rates to the system performance, i.e., dynamic performance, especially in the overloading situation. The parameter setting is the same as the former except that the arrival rate changes in the range of 50-350 frame/s.As shown in Figure5, when the system capacity is unsaturated (50-250 frame/s), the throughput is proportional to the growth of the arrival rate for all protocols. The features of power consumption and energy efficiency present similar characteristic with Section 5.1. After that, robots suffer from traffic bursting which leads to distinct performance in the four protocols.Figure 5
Dynamic performance along with arrival rate.
(a)
Throughput
(b)
Power
(c)
Energy efficiencyFor 802.15.4, FD-MAC, and MQEB-MAC, network congestion occurs, and the system performance is reduced because of the noncongesting protection mechanism. Data loss will consume extra energy and lead to the degradation of throughput and energy efficiency. On the contrary, thanks to the admission control, the Two-Tier MAC could reject new frames when the network is overloading to avoid network congestion. So the energy efficiency can be maintained even in this severe network environment.


## 6. Conclusion

Considering the heterogeneity on both robots and frames, a two-tier hierarchical-based MAC is proposed to guarantee the differentiated QoS performance and maximize the system throughput. Experiments show that compared with IEEE 802.15.4, FD-MAC, and MQEB-MAC, the Two-Tier MAC can improve the overall throughput by the Lyapunov theory, reduce power consumption by the time slot isolation scheme, and expend system lifetime by the energy balance. Even in the overloading condition, the QoS performance can be guaranteed thanks to the admission control.In the future, we would like to do more work to find the close-formed solution for the optimized problem instead of the heuristic algorithm. In addition, in this paper, all robots operate task offloading to the central cloud which suffers from large end-to-end delay. Along the development of 5G, offloading in the distributed mobile edge computing (MEC) scenario should be studied in the future.



---

*Source: 8876705-2020-08-28.xml*