Research On Algorithms For Real-time Transmission And Scheduling In Cyber Physical Systems

Cyber-Physical System(CPS)is a large scale and distributed heterogeneous system,which collaborating computing,communicating,sensing and controlling.A typical CPS consists of four parts,i.e.,sensor networks,actuators,controllers and gateway equipments.Since it can highly integrate the information computation and physical world through real-time,reliable,cooperative and safe sensing and controlling the environment,it has been widely used in military defense and social life.In CPS,the captured and calculated information by sensor networks is transmitted to the user or terminal through multi-hop transmission.After that,the feedback control commands can be generated according to the captured information.During this process,the real-time data transmission and scheduling is very essential.For example,in the safety critical military and environment monitoring system(such as target detection and tracking in battlefield,medical surveillance and chemical and radioactive elements detection),the captured information and control commands must arrive at the terminal within the deadline limit,so that the system can timely response to avoid the serious consequences.On the other hand,when the nodes works in the duty-cycled mode to conserve energy and prolong network lifetime,the delivery latency grows dramatically.However,real-time data delivering is not well studied in such network.Therefore,this dissertation will study the real-time transmission,data aggregation and scheduling in duty-cycled sensor networks.The research issues and contributions of this thesis are summarized as follows.Firstly,this thesis investigates the design of end-to-end real-time routing algorithm for CPS.Real-time routing is very essential for many applications and operations in CPS.To achieve the arbitrary end-to-end real-time routing in asynchronous duty-cycled sensor networks,a dynamic switching based real-time routing protocol(DSRT)is proposed firstly.In DSRT,the concept of available speed is designed to facilitate discovering the routes with less latency based on two-hop neighbors' information(at lease about 20%routing path with less latency is discovered by DRST in the experiments).Moreover,it is noticed that the congestion extent in the low-duty-cycle network was determined not only by the number of packets in the network output queue,but also the destination of the packets.However,the traditional method cannot differentiate this kind of congestion.Therefore,combined with the dynamic switching mechanism,the DSRT proposes a congestion avoiding algorithm by classifying the packets in the queue.In addition,considering the unreliable wireless transmission,an active slot augmentation based routing protocol framework(RRAD)is proposed.By exploiting active slot augmentation and ARQ-based reliable routing mechanisms,DSRT efficiently reduces the extra sleep latency caused by unreliable links.Through experiments,the end-to-end delay can be decreased by at least one time with such mechanisms.Moreover,by exploiting the asynchronous waking up time in duty-cycled networks,a lightweight potential forwarder discovering algorithm is proposed in RRAD to offer nodes another chance to be the forwarder.We demonstrate the efficiency of the proposed DSRT and RRAD protocol in term of routing latency and reliability through comprehensive experiments.Secondly,this thesis investigates the energy-efficient and delay-bounded multicast scheduling problem for CPS.Multicasting is a fundamental network service for one-tomany communications in CPS.However,when the sensor nodes work in an asynchronous duty-cycled way,the sender may need to transmit the same message several times to one group of its neighboring nodes,which complicates the minimum energy multicasting problem.Thus,in this paper,the problem of minimum energy multicasting for dutycycled sensor networks is studied and is proved to be NP-hard.To solve such a problem,the concept of an auxiliary graph is proposed and a greedy algorithm is proposed to construct such a graph.Based on the proposed auxiliary graph,an approximate scheduling and constructing algorithm with an approximation ratio of 4ln K is proposed,where K is the number of destination nodes.On the other hand,since nodes can receive data only when it is in active state in such networks,the communication delay can be extremely large.However,most of the existing methods didn't consider how to control such big delay in multicasting energy efficiently.Due to such reason,the problem of delay-bounded multicast scheduling is also studied,which seeks to reassign minimal active time slots to bound the delay for a multicast request.A dynamic programming method is proposed to minimize the required number of augmented active time slots.The theoretical analysis and experimental results verify the efficiency of the proposed algorithm in term of energy cost,transmission redundancy and real-time service.Thirdly,this thesis investigates the minimum latency data aggregation problem for CPS.Data aggregation is an essential operation for the sink to obtain summary information in CPS.The problem of Minimum Latency Aggregation Schedule(MLAS)which seeks a fastest and collision-free aggregation schedule has been well studied when nodes are always awake.However,in duty-cycled sensor networks,nodes can only receive data in active state.In such networks,it is of great importance to exploit the limited active time slots to reduce aggregation latency.Unfortunately,few studies have addressed this issue and most previous aggregation methods rely on fixed structures which greatly limit the exploitation of the active time slots from other neighbors.Therefore,the MLAS problem in duty-cycle WSNs without considering structures in studied.The first distributed aggregation algorithm for duty-cycle sensor networks is proposed,in which the aggregation tree and a conflict-free schedule are generated simultaneously.Then we prove the proposed algorithm has an aggregation latency bound of (?),where C is the duty cycle,? = |2?/arccos(1 + 1/?)|,? is a positive number in [0.05,1],R is the radius of the network,and ? denotes the maximum node degree.The simulation results verify the aggregation latency and the utilization ratio of available time slots can be improved by 1 time.Finally,this thesis investigates the problem of minimum latency beacon scheduling for CPS.Beaconing is a fundamental networking service where each node broadcasts a packet to all its neighbors locally.Unfortunately,the problem Minimum Latency Beaconing Schedule(MLBS)in duty-cycled scenarios is not well studied.Existing works always have rigid assumption that each node is only active once per working cycle.Aiming at making the work more practical and general,MLBS problem in duty-cycled network where each node is allowed to active multiple times in each working cycle(MLBSDCA for short)is investigated in this paper.Firstly,a modified first-fit coloring based algorithm is proposed for MLBSDCA under protocol interference model.After that,a(? + 1)2· ||-approximation algorithm is proposed to further reduce the beaconing latency,where ?denotes the interference radius,and || is the maximum number of active time slots per working cycle.When ? and || is equal to 1,the approximation ratio is only 4,which is better than the one(i.e.,10)in existing works.Furthermore,two approximation algorithms for MLBSDCA under physical interference model are also investigated.The simulation results verify the beaconing latency can be improved by 2 times by the proposed methods.