Research On Scheduling Algorithms For Diverse Communication Requests On Wireless Networks

As the continuous developing of wireless communication technology,the enriching of functions on mobile devices,and the wide adoption of embedding techniques,wireless networks have been supporting the underlying information flows in numerous scenarios.Within these scenarios,there are participators with diverse behaviors.For example,smart device holders using various applications,different sensors running different monitoring tasks,and different actuators controlling multiple functions.Besides bringing in together a huge scale of data flow,these participators also have diverse and complicated objectives,which in turn lead to different data flow and communication requests.For instance,par-ticipators running video streaming service request a smooth data transmission,while the participators acquiring the location information expect a real-time and reliable response.This phenomenon poses a series of novel challenges for the design and resource allocation in wireless networks,which requests a novel design on link-layer data transmission and scheduling,network topology control,MAC layer protocols,application-layer resource allocation and many others.Among all these aspects,link-layer data transmission and scheduling is one of the most critical components.A scheduling policy refers to the set of device pairs to transmit in each time unit,when given network parameters like cur-rent channel condition and conflicting among links.More specifically,the scheduling policy can determine the portion of resource assigned for each participator according to her request,so as to maintain the normal process of the whole system.However,cur-rent scheduling policies still focus on achieving the maximum throughput or Quality of Service(QoS)on links,and need to be further improved.Several drawbacks for current scheduling policies are:1)they request some homogeneity on the behaviors of participa-tors,cannot be adapted to diverse behaviors.2)all the scheduling policies still evaluate the network performance based on the service on every link.They fail to capture the service received by each application in the scenario,and they also cannot allocate the resource to maintain the normal processing of these applications.3)considering that participators are often individuals,these policies cannot be correlated with individuals’ user experience,especially when the network bandwidth is fully charged.Consequently,this dissertation focuses on handling the diversity of participators,where the diversity mainly occurs on the communication model,requests on single links,the process of applications,and main-taining the quality of experience among diverse participators.A series of contributions are proposed in this dissertation,which is shown as follow.(1)The design of scheduling algorithm for diverse multicast sessions is studied in this dissertation.Considering that current analysis on multicast communication all as-sumes there are some homogeneity among the sessions,this dissertation analyzes in chap-ter 2 the network performance under multicast sessions with arbitrary number of destina-tions and ranges,and designs a corresponding scheduling algorithm to achieve the optimal performance.Firstly,a novel network model is proposed,which allows each participa-tor in the network to select an arbitrary number of destinations in an arbitrary circle area around it.This model is more practical for the real networks with diverse sessions.Based on the model,this dissertation derives an upper bound on the network capacity,which is a measurement on the general throughput of the network.A novel metric describing the degree of competition on network resource is introduced to support the analysis.Subse-quently,an existing scheduling algorithm is extended for the transmission of all multicast sessions,and proves that the achievable network capacity of this algorithm is in the same order with the proved upper bound.Finally,simulation results show how the diversity of multicast sessions impact the network capacity.(2)The design of scheduling algorithm for links with diverse service frequency re-quests is investigated in this dissertation.Considering that current solutions fail to handle this challenge,this dissertation proposes in chapter 3 a novel framework that can guar-antee the service frequency for each device,while also achieving a high network utility.Firstly,a novel network model and the definition on network stability is proposed,which includes the performance on the service frequency.The design of optimal scheduling algorithm is proved to be NP-complete.Then a novel approximation scheduling algo-rithm is proposed,which is a composition of two state-of-the-art scheduling policies.This algorithm maintains the service frequency for each device while also achieving a good network utility.Furthermore,it is proved that the proposed algorithm is optimal in collocated networks,and analyzes the impact of service frequency on both network per-formance and the queue length for single device.Finally,numerical results demonstrate that the proposed algorithm outperforms existing results.(3)The design of scheduling algorithm for applications with diverse data commu-nication requests is studied in this dissertation.Considering that current scheduling poli-cies still focuses on the link-layer performance,this dissertation studies in chapter 4 the solutions for scheduling tasks from multiple applications with diverse request on data transmission.Firstly,a novel definition on the network stability is proposed,which can capture the transmission of each task.More specifically,a new metric is defined for the minimum number of transmitted packets for each task at a given slot,so as to support the normal process of the application.This metric can be used to cover the diversity of data communication requests for different applications.This dissertation then proves the design of an optimal scheduling algorithm to be NP-complete,and gives a scheduling algorithm.The algorithm can adaptively maintain the priority for each task,while also achieving a high utility.After that,this dissertation also analyzes the performance of the algorithm,can show its optimality in collocated networks.The design of optimal solution in general wireless networks is also discussed.Finally,extensive simulation results reveal that the proposed scheduling algorithm can improve the performance of transmission on each application.(4)The scheduling algorithm maintaining user experience under diverse data com-munication requests is investigated in this dissertation.Since existing work cannot bal-ance the user experience with diverse data flows,this dissertation is designed to mitigate this gap in chapter 5.The proposed framework tries to serve a maximum number of par-ticipators while maintaining good experience for them.An improved network model is designed,which can capture the diverse data transmission requests,while allowing a guar-antee on the experience.Meanwhile,the network stability is defined based on the total number of served participators.Based on the proposed network model,it is first proved that the design of an optimal algorithm is NP-complete,and a two-phases scheduling al-gorithm is proposed.The algorithm can determine the assignment of new participators,and allocate the network resource for all the assigned participators.The complexity and the performance of the algorithm is then analyzed.Finally,the simulations results demon-strate that both user experience and total number of served participators are improved in the derived scheduling policy.