Age of Transmission-Optimal Scheduling for State Update of Multi-Antenna Cellular Internet of Things

Song Li,Min Li,Ruirui Chen,Yanjing Sun,2,3

1 School of Information and Control Engineering,China University of Mining and Technology,Xuzhou 221116,China

2 Artifcial Intelligence Research Institute,China University of Mining and Technology,Xuzhou 221116,China

3 Xuzhou Engineering Research Center of Intelligent Industry Safety and Emergency Collaboration,Xuzhou 221116,China

Abstract:Timely information updates are critical for real-time monitoring and control applications in the Internet of Things(IoT).In this paper,we consider a multi-antenna cellular IoT for state update where a base station(BS)collects information from randomly distributed IoT nodes through time-varying channel.Specifcally,multiple IoT nodes are allowed to transmit their state update simultaneously in a spatial multiplex manner.Inspired by age of information(AoI),we introduce a novel concept of age of transmission(AoT)for the sceneries in which BS cannot obtain the generation time of the packets waiting to be transmitted.The deadline-constrained AoT-optimal scheduling problem is formulated as a restless multi-armed bandit(RMAB)problem.Firstly,we prove the indexability of the scheduling problem and derive the closed-form of the Whittle index.Then,the interference graph and complementary graph are constructed to illustrate the interference between two nodes.The complete subgraphs are detected in the complementary graph to avoid inter-node interference.Next,an AoT-optimal scheduling strategy based on the Whittle index and complete subgraph detection is proposed.Finally,numerous simulations are conducted to verify the performance of the proposed strategy.

Keywords:age of transmission;information freshness;cellular IoT;restless multi-armed bandit;Whittle index

I.INTRODUCTION

The ffth-generation mobile communication technology(5G)based cellular Internet of Things(IoT)has been widely used in various IoT applications,such as smart city and intelligent transportation because of low power consumption,low cost,and wide coverage[1].In cellular IoT,massive sensors collect various parameters of the environment,machines or human in a realtime manner and send the updated data to the control center,which then makes decisions based on the updated data.Thus,the freshness of the information received by the control center has a signifcant impact on the accuracy of its decision,since receiving outdated information at the destination may reduce the accuracy and reliability of remote control system[2].

To effectively measure the freshness of information in the IoT,age of information(AoI)is proposed as a new metric in IoT,which is defned as the time elapsed since the generation of the most recently delivered packet from the perspective of the destinations[3–5].Unlike transmission delay,AoI not only includes the time for data transmission but also the time duration waiting for transmission after the data generation.To facilitate the analysis and optimization of AoI in a cellular IoT system,the transmitted packets need to be timestamped.In other words,the generation time of the packet should be included in the transmitted packet and transmitted together with the update data,thus the base station can calculate the AoI of the cellular IoT system.

In the past few years,AoI has attracted great attention and has been studied in various scenarios.Queuing model is applied to analyse AoI in real-time system in[6–9].An optimal control problem for state updating of a system where the source node was comprised of a frst in frst out queue and two applications was studied in[6].The explicit formulas for the Laplace Stieltjes transformation of the stationary distributions of AoI and peak AoI(PAoI)in frst-comefrst-served(FCFS)M/GI/1 and GI/M/1 queues were derived in[7].In a single-source scenario,the bufferless PH/PH/1/1/P(p)queue and a single buffer M/P H/1/2/R(r)queue with probability preemption were considered,and a numerical algorithm for obtaining the exact distributions of AoI and PAoI was proposed in[8].The AoI in a single server queue with four different service disciplines,including FCFS,preemptive last-come frst-served(LCFS),and two variants of non-preemptive LCFS was analyzed in[9].

The AoI-oriented scheduling strategy is also getting more and more attention from researchers[10–14].Considering an AoI orchestration agent for link scheduling in D2D-enabled industrial wireless networks,a learning-based autonomous AoI and power orchestration agent was proposed in[10].The maximum average throughput optimization for a single user in a fading channel under average AoI and power constraints was studied in[11].In a single-hop network,a scheduling strategy was designed to minimize the total expected AoI in[13].A weighted graph was constructed to design an optimal scheduling strategy to minimize the cost function of AoI in a multi-source system in[14].

The Whittle index-based scheduling provides an effective solution for AoI-oriented scheduling problems with low computational complexity[15–19].An index policy for AoI optimization which considers stochastic packet arrivals and optimal packet management was proposed in[16].By comparing greedy algorithm,Whittle index strategy,maximum weight algorithm,and random strategy,the Whittle index strategy and maximum weight algorithm outperform other benchmarks according to[17].In the multi-users regime for the AoI minimization problem,the optimality of the Whittle index strategy had been proved in[18].A request-aware scheduling policy for static and dynamic request models was considered in[19].The study in[20]shows that the Whittle index strategy was nearly optimal in performance,and the strategy’s performance was higher when the number of terminals was larger.The authors in[21]studied the scheduling problem of AoI optimization in star topology wireless network and found that the performance of indexprioritized random access strategy with a single packet buffer was close to the optimal and higher than the general random access strategy.

However,most of the above studies consider the problem of scheduling one IoT node in each time slot.In a multiple-antenna IoT system,multiple IoT nodes can be scheduled in one timeslot by spatial multiplexing under a certain interference management mechanism.Furthermore,for some IoT systems,the generation time and corresponding deadline of data are known to the IoT nodes.However,the receiver(base station)can not know the generation time of its received data,only the transmission time,since the data are not timestamped.Therefore,for these IoT systems,the AoI cannot be calculated accurately to measure the freshness of data.With this in mind,we introduce a novel concept age of transmission(AoT),which is defned as the time elapsed since the latest update information was successfully transmitted.We investigate an AoT optimal scheduling problem in a multiantenna cellular IoT system.The outage probability of update data transmission is derived considering the impact of channel state information and co-channel interference.Then,the deadline-constrained scheduling problem is modeled as a restless multi-armed bandit(RMAB).We construct an interference graph considering the inter-node interference and propose a Whittle index-based scheduling strategy considering the complete subgraph.Therefore,the main contributions of this paper are as follows.

·We investigate the AoT optimization in a multiantenna cellular IoT system in which multiple IoT nodes can transmit their sensing data to the base station(BS)simultaneously.The outage of each IoT node is derived as a function of the received signal-to-interference and noise ratio(SINR).

·The deadline-constrained AoT optimal scheduling problem is formulated and an RMAB framework for this scheduling problem is presented.The indexability of the RMAB problem is proved and the closed-form expression of each IoT node’s Whittle index is derived.

·The interference graph and corresponding complementary graph are constructed based on the interference relationship between each two IoT nodes.The node sets which can scheduling simultaneously are modeled as complete subgraphs in the complementary graph.Then a Whittle indexbased scheduling strategy is proposed in which an IoT node set corresponding to a complete subgraph is scheduled considering the sum Whittle index of each complete subgraph.

The rest of this paper is organized as follows.We describe the system model in section II.In section III,we formulate the scheduling problem as an RMAB problem.In section IV,we derive the closed-form expression of the Whittle index and prove the indexability.In section V,we propose a Whittle index-based scheduling strategy.The simulation results based are introduced in section VI.Finally,we conclude this paper in section VII.

II.SYSTEM MODEL

2.1 Channel Model

Consider a multi-antenna cellular IoT with a BS receiving updated states fromNIoT nodes,where BS is equipped withMreceiving antennas and the IoT nodes are equipped with a single transmitting antenna.The SIMO uplink transmission is considered in this paper,where each IoT node transmits its data via one transmitting antenna and the BS receives the data via multiple receiving antennas.The transmission time is divided into discrete time slots.Suppose that the channel state remains stable in one timeslot and varies independently in different time slots.h(t)denotes channel state information(CSI)between BS and all IoT nodes,whereThe vectorhn(t)=[hn,1(t),hn,2(t),···,hn,M(t)]denotes the channel gain vector from IoT nodento the BS in the time slott,n ∈{1,2,···N}.At the beginning of each time slot,the scheduled IoT node sends the latest updated data to the BS.Assume the updated data can be sent within one timeslot,such as vehicle instantaneous acceleration,ambient temperature,and soil moisture.

Since the BS is equipped with multiple antennas,and multiple IoT nodes can send sensing data to the BS in the same frequency.Assume that the set of IoT nodes sending updated data to the BS in time slottisO(t),and the data received by the BS can be expressed as

wheresn(t)represents the signal transmitted by the IoT nodenandn(t)is the interference noise.

Assume after BS received transmitted data from multiple IoT nodes,certain signal processing methods can be used to decode data from each IoT nodes,such as zero forcing(ZF),minimum mean square error restoration(MMSE).In this paper,ZF fltering is adopted to decode the data which is sent by IoT node,and the corresponding flter vector[22]is expressed as

where the frst term of Eq.(3)is the expected signal from IoT noden,the second term is the interference caused by other nodes,and the third term is additive white Gaussian noise.

Denotepnas the transmitted power of IoT noden.The received SINR for IoT nodenat BS can be given by

Supposeγthdenotes the SINR threshold required by the BS to decode successfully.Whenγn ＜γth,BS cannot correctly decode the data from IoT nodenand an outage occurs for IoT nodenin this time slot.The outage probability of IoT nodenis expressed as[23]

2.2 Transmission Model

The IoT nodes collect the parameters of the environment or device and then update their states according to the sensing result.We assume that the data generated by IoT nodes follows the Bernouilli process with parameterλ.After the data is generated in each IoT node,we denotednas the deadline for the data andτnas the corresponding timestamp for IoT noden.Each IoT node will not generate new data if the current time slot is not the deadline of the data waiting for transmission.The data will lose its timeliness while it exceeds the corresponding deadlines,and a new one will be generated.

Denotexn(t)as the schedule decision of the BS.If IoT nodenis scheduled at time slott,xn(t)=1,otherwise,xn(t)=0.If the transmission of sensing data is successful,the IoT nodenwill generate a new sensing data with probabilityλ.If the transmission in time slottfails or the IoT node is not scheduled,the state of IoT node is described as follows.

1.Ift-τn ≤dn,the sensing data in IoT nodenneeds to be retransmitted in the next time slot.

2.Ift-τn ＞dn,the IoT nodendrops the current sensing data and collects the current state,and updates sensing data.

Note that,in the cellular IoT system considered in this paper,the state of each IoT node is assumed to vary slowly.In other words,the state of each IoT node can be considered to be static in a short duration.Thus,the sensing data in each IoT node waiting for transmission can still represent the current state before the corresponding deadline.In this case,the waiting time before transmission does not affect the timeliness of data.When the waiting time for transmission exceeds the corresponding deadline,the current sensing data of each IoT node will be dropped and new sensing data will be updated.

2.3 AoT Model

The age of transmission(AoT)depicts the freshness of the information in IoT nodes from the perspective of the BS.DenoteAn(t)as the AoT with respect to IoT nodenat time slott.An(t)grows linearly as time goes by,and drops to one when BS gets the updated information.We initializeAn(0)=1.The evolution of AoT can be written as

where Λnis an indicator variable which represents whether the IoT nodenis transmitted correctly.Λn=1 means that the IoT nodenis scheduled and successfully transmits data to BS.

The motivation for introducing the concept of AoT is as follows: In an IoT system in which the information is not timestamped,the receiver cannot obtain the data generation time,only the transmission time.AoT can be considered as a simplifed version of AoI,which ignores the waiting delay of information before transmission.Moreover,the waiting delay is constrained by the deadline of generated data.If the data generated on IoT nodenis not transmitted before the deadline,the data will be discarded and new data will be generated at the IoT noden.Thus,the relationship between AoI and AoT can be expressed as AoT＜AoI＜AoT+d,wheredis the deadline.

III.PROBLEM FORMULATION

DenoteBn(t)=t-τnas the waiting time for sensing data in IoT noden.If there is no packet in IoT noden,we have thatBn(t)=0.DenoteS(t)Δ={s1(t),s2(t),···,sN(t)}as the system state,wheresn(t)=(An(t),Bn(t))represents the state of IoT nodenat time slott.The state transition probability of IoT nodenin the next time slot is discussed as follows.

1.IfBn(t)=0,there is no sensing data waiting to be transmitted in IoT node,and the state transition probability is expressed as

2.IfBn(t)+1＜dn,the state transition probability when IoT nodenscheduled is described as

When IoT nodenis not scheduled,we can have

3.IfBn(t)+1≥dn,the state transition probability when IoT nodenscheduled is described as

When IoT nodenis not scheduled,the sensing data in next time slot will be expired,and a new perceptual data will be generated,i.e.,

The rewardrn(t)obtained by the BS after taking the actionxn(t)can be expressed as:

whereCn(t)is the reward of IoT noden.The logistic function(1+eεAn(t))-1represents the timeliness of data andεis a constant.P(Bn(t)+1≥dn)represents whether the sensing data reach its deadline,whereP(x)is an indicator.Ifxis true,P(x)=1.Otherwise,P(x)=0.When the information exceeds its deadline and a penalty will be incurred with valueφ.

In each time slot,the multi-antenna cellular IoT can support multiple IoT nodes to access simultaneously in a spatial multiplex manner,which means,up toKIoT nodes can be scheduled by BS simultaneously.The maximum value ofKis dependent on the freedom degree of the multi-antenna system.ThusKis an integer which is no more than min(M,N),whereMis the number of antennas in BS andNis the number of IoT nodes.The objective of this paper is to design the scheduling strategy to maximize the total discounted reward of the system,i.e.,

whereπ′denotes a feasible strategy,Tis the time horizon andβ(0＜β ≤1)is the discount factor.

IV.WHITTLE INDEX DERIVATION

The scheduling problem of IoT nodes for AoT optimization can be formulated as a constrained Markov decision process(MDP)with fnite state spaces.The decision made by each IoT node in the current timeslot is only related to the current state.However,the state space of the scheduling problem increases exponentially with the increase of the network size.It means that the MDP model suffers from the curse of dimensionality.Therefore,we can reformulate the IoT node scheduling problem as an RMAB problem where each arm represents one IoT node and corresponding rewards will be derived as the player pulls an arm.In general,the RMAB problem is PSPACE-hard[24].Whittle index policy provides a near-optimal solution to RMAB by considering the Lagrangian relaxation of the problem[20,21].According to Whittle index policy,arms are decoupled when computing the index,and the originalN-dimensional problem is decoupled intoNindependent 1-dimensional problems.As a consequence,the complexity of fnding the optimal policy for an RMAB is reduced to linear withN.

We frst investigate the problem that only one IoT node is allowed to be scheduled.Lagrangian relaxation approach is adopted to relax problem and a Lagrange multipliervis defned for the constraint Eq.(14),which can be seen as a subsidy for not scheduling.The Lagrange function equals to

Then,we decouple theN-dimensional problem intoNsub-problems.When only one IoT node is considered,the subscriptnin the formula can be omitted and the one-armed reward ofv-subsidy can be expressed as

According to Eq.(34),calculating the Whittle index does not require the exact value ofB,but only needs to know whetherBis greater thand.This means that even the transmission data of each IoT node is not timestamped,the BS can also calculate the Whittle index of each IoT node and perform a proper schedule strategy to maximize the expected reward.The base station can lean whether the data in each IoT node exceeds its deadline in the following ways: The IoT nodes whose data will expire in the next time slot will send an expiration indicator to the BS in the current time slot.

V.AOT-OPTIMAL SCHEDULING STRATEGY

5.1 Interference Graph Construction

5.2 Complete Subgraph Detection

Since the Whittle index of each node can indicate the priority of the node being scheduled,the weight of a node in the interference graph can be defned as the Whittle index of the node.The scheduling process of each time slot can be modeled as detecting the independent set with maximum sum-weighted in the interference graph.In this section,we transform the problem of detecting the largest independent set in the interference graph into the largest complete subgraph problem in the complementary graph.

LetG′=(V,O′)denotes the complementary graph of the interference graphG=(V,E),where the set of edgesO′in the complementary graph is defned as follows.

Definition 3.Complete subgraph is a subgraph that has exactly one edge between each pair of different vertices.

According to defnition 3,the problem of detecting the largest independent set in the interference graph is equivalent to the problem of detecting the largest complete subgraph in the complementary graph.We frst investigate the algorithm for detecting all complete subgraphs in the complementary graph,then a Whittle index-based scheduling strategy is proposed based on the complete subgraphs detected.

According to graph theory,the complete subgraphs detection algorithm in the complementary graph is proposed in Algorithm 1.

Denoteo′as the adjancency matrix of complementary graphG′=(V,O′)and arrange the degree of each line ofo′in descending order{de1,de2,···,den}.Denote A as the set of nodes which includes nodenand have edges between any two nodes and B as the set of nodes that have edges with the nodes in A.The main steps of complete subgraph detection are as follows.

1.Denote the size of the largest complete subgraph ask.Select node{n}arbitrarily,and move the nodes from B to A in turn,and delete the nodes which have no edge with the IoT node in A.

Algorithm 1.Complete subgraph detection algorithm of complementary graph.Require: o′;Ensure: k,A;1: if dek ＞k-1 then 2: return k 3: end if 4: for i=k;i ＞1;i--do 5: initialize A,B;6: for each node n ∈[1,N]do 7:A={n,A};8:if o′(x,y)= 1, x ∈A, y ∈[1,x)∪(x,N]then 9:B={y,B};10:end if 11:for each node m ∈B do 12:A={m,A},B=Bm;13:if o′(x,y)=0,x ∈A,y ∈B then 14:B=By;15:end if 16:end for 17:if|A|＜i,|B|=0 or|A|＞i then 18:stop detecting;19:else if|A|=i then 20:return A;21:end if 22: end for 23: end for

2.When the size of A is smaller thank,and B is an empty set or there is a larger complementary graph in A,the detecting is stopped and returns to step(1).Otherwise,when|A|=k,a new complete subgraph A with sizekis generated,we record it and return to step(1).

3.k=k-1,repeat the above steps,and record all complementary graphs.

5.3 Whittle Index Based Scheduling Strategy

According to the defnition of the Whittle index,the higher the Whittle index each IoT has,the more attractive the IoT node is to the BS.In a freshness-sensitive cellular IoT,one or more IoT nodes with higher Whittle index should be scheduled for data transmission.Thus the weight of each vertex inGandG′is defned as the Whittle index of the corresponding IoT node.In each time slot,multiple IoT nodes with maximum sum weight should be scheduled.In addition,the scheduled nodes should not cause interference to each other,which means the scheduled IoT nodes should form a complete subgraph in the complementary graph.Based on the complete subgraph obtained in Algorithm 1,we propose an AoT-optimal scheduling strategy based on Whittle Index and Complete Subgraph detection(WICSD)in Algorithm 2.

Algorithm 2.AoT-optimal scheduling strategy based on Whittle Index and Complete Subgraph detection(WICSD).Require: complete subgraphs set S;Ensure: Sx;1: for each node n ∈[1,N]do 2: calculate Whittle index vn accroding to Eq.(34),weightn =vn;3: end for 4: for i=1;i ＜|S|;i++do 5: if|Si|＞K then 6:S=SSi;7: else if|Si|≤K then 8:calculate sum(weight(Si));9: end if 10: end for 11: fnd the maximum sum-weight Sx;12: return Sx;

Denote S ={S1,···S|S|}as complete subgraphs set,detected according to Algorithm 1.At any time slott,the Whittle index of the IoT node is calculated according to Eq.(34)and is taken as the weight of the node.Since at mostKnodes can be scheduled in each time slot,the node number in each subgraph cannot be larger thanK.Thus,in the complete subgraph detection,we frst fnd the complete subgraph with sizeK.Then iterative method is used to fnd the complete subgraphs of smaller size,and the complete subgraphs whose size are larger thanKare ignored.Select the complete subgraph Sxwith the maximum sum weight and all the IoT nodes corresponding to this subgraph are scheduled in this time slot.

Assume that the total number of nodes isN,the number of edges ise,and the number of complete subgraphs in the complement graph isa.The complexity analysis of the proposed WICSD strategy is as follows: When the Whittle index of each IoT node in Algorithm 2 is calculated,the execution time isO(N).When detecting all complete subgraphs,the execution time of Algorithm 1 to traverse all nodes in the com-plementary graph isO(N),and the execution time of traversing all nodes in the network to search for other complete subgraphs isO(e).Thus the execution time required by Algorithm 1 isO(Ne).When deleting the complete subgraph whose size is greater thanK,a complete subgraph needs to be traversed,and the execution time isO(a).When Algorithm 2 executes the last step,at mostacomplete subgraph meets the condition,and the execution time isO(a).Then the total execution time of the Whittle index scheduling strategy based on the complete subgraph isO(N)+O(Ne)+O(a)+O(a)=O(Ne).

VI.PERFORMANCE EVALUATION

In the simulation,we compare the performance of the proposed WICSD strategy with the earliest deadline frst(EDF)[26],least laxity frst(LLF)[27]algorithm.The EDF algorithm mainly deals with thektasks with the earliest deadline in each time slot.The LLF algorithm determines the priority of the task according to the urgency(laxity)of the task.The higher the urgency of the task,the higher the priority given to the task by the scheduler.The simulation parameters are shown in Table 1.

Table 1.Simulation parameters.

Since the instant discounted reward eventually tends to 0 as the time slot changes,the total rewards concerning different system parameters are simulated and analyzed in this section.Figure 1 shows the total reward,while the BS can schedule up to 4 nodes among 12 IoT nodes.By comparing the WICSD strategy based on the complete subgraph with the EDF,LLF algorithm,we can see that the performance of the WICSD strategy is better than that of the other two benchmark algorithms and the performance gain is larger as time goes by.

Figure 1.The total rewards of the index-based scheduling algorithms,EDF,and LLF algorithms.

Figure 2.Total reward v.s.the data arrival rate.

In Figure 2,we consider heterogeneous data arrival patterns,i.e.,one IoT node has stochastic data arrival and the index is calculated by Eq.(35).It is observed that the WICSD strategy’s performance is better as the arrival rate increases.When the processing capacity of the system is abundant,the higher the data arrival rate,the fewer empty IoT nodes scheduled by the system per time slot.

The performances of the three strategies under different values ofKare illustrated in Figure 3,and we simulate the relationship between the schedulable numberKand the system reward.Assume there are 8 antennas on BS and BS selectsKscheduling node from 20 IoT nodes.The WICSD strategy shows better performance than that of the other two benchmark algorithms and the total reward becomes larger asKgradually increases from 3 to 8.

Figure 3.Total reward v.s.number of simultaneous transmissions K.

Figure 4.Total reward v.s.number of users N.

Figure 5.Total reward v.s.power.

Figure 6.Total rewards of the index strategy and exhaustive searching.

As shown in Figure 4,the number of antennasMis set to 4,the maximum schedule numberk= 4.With the increase of the number of IoT nodes,the rewards of all the algorithms are decreasing and WICSD strategy achieves the highest reward.When the number of IoT nodes is greater than 12,the range of total reward increases with the increase of total nodes.This is due to the fact that the amount of data waiting to be transmitted per time slot is increasing as the number of IoT nodes increases.

Figure 5 shows the simulation result of the transmission power in IoT nodes.As the transmit power gradually increases,the rewards of all the algorithms are increasing and WICSD strategy achieves the highest reward.When the transmission power is greater than 4,the change of total reward tends to 0.This is due to the fact that the outage probability changes slowly when the transmitted power is high enough.

The total reward of the WICSD strategy is compared with that of the exhaustive searching,as shown in Figure 6.The exhaustive searching algorithm can provide optimal performance among all available scheduling algorithm,in whichKIoT nodes with maximum total rewards are scheduled considering co-channel interference.The total number of IoT nodesNis set to 20.According to the simulation results,the performance of WICSD strategy is slightly worse than the performance of exhaustive search in terms of total reward.However,the computational complexity of WICSD strategy isO(Ne),which is signifcantly lower than that of the exhaustive searching algorithm.

VII.CONCLUSION

In this paper,the state update in multi-antenna cellular IoT is investigated.The deadline constrained AoT optimization problem is formulated as an RMAB problem,and the closed-form expression of the Whittle index is derived.Furthermore,an AoT-optimal scheduling strategy based on Whittle index and complete subgraph detection(WICSD)is proposed considering co-channel interference,by constructing interference graph and complementary graph among all IoT nodes.The simulation results show that,compared with other benchmark algorithms,the proposed strategy improves the reward of the system and avoids inter-node interference while allowing multiple IoT nodes to transmit simultaneously.

ACKNOWLEDGMENT

This work was supported by the Fundamental Research Funds for the Central Universities(2020ZDPYMS26),the National Natural Science Foundation of China(62071472,51734009),the Natural Science Foundation o Jiangsu Province(BK20210489,BK20200650),China Postdoctoral Science Foundation(2019M660133),the Future Network Scientifc Research Fund Project(FNSRFP-2021-YB-12),and the Program for “Industrial IoT and Emergency Collaboration” Innovative Research Team in CUMT(No.2020ZY002).