无线网络多样性通信请求的调度算法研究

发布时间：2018-05-28 05:41

本文选题：数据通信 + 多样性　；参考：《哈尔滨工业大学》2017年博士论文

【摘要】：伴随着无线通信技术的不断发展、移动设备功能的不断增加、以及嵌入式技术等关键技术的不断普及和应用,3G/4G手机网络、WiFi网络、D2D网络等无线网络成为了支持各种场景中信息流通的核心渠道之一。这些场景引入了更多行为存在多样性的参与者,例如运行不同应用的智能设备持有者、不同作用的感知部件、控制部件等。这些参与者在产生大规模的信息流通的同时,通常有各异的并且复杂的行为目的,因此相应的会产生多种多样的数据通信要求。这对无线网络的设计和资源调配提出了一系列新的挑战,需要对包括链路层数据传输调度、网络结构拓扑设计、媒体存取控制层协议、应用层资源分配在内的多个方面进行重新思考。其中链路层数据传输调度方案是关键环节之一,它在给定网路中各链路的信道质量、冲突情况等因素的前提下,确定在各个时间段内进行传输的设备对。更具体的,链路层数据传输调度方案能够根据各个参与者的通信请求,在不同网络环境和通信负载下合理为各个参与者分配传输资源,从而保证这些场景下系统的正常运行。然而,现有的数据传输调度方法还不够完善,仍以最大化网络利用率、保证链路质量等作为主要优化目标,存在着一些缺陷,主要有以下几点:第一,这些方法需要确保参与者行为某种程度的一致性,不能对多样性的情况进行分析和给出相应的传输资源分配方案;第二,这些方法主要从单条链路所获服务衡量整个系统的性能,不能从场景中不同应用所获得的服务进行评估,同时给出相应的确保各应用正常运行的传输资源分配方案;第三,考虑到参与者时常为请求各异的个人,这些方法很难去直接同参与者的用户体验相联系,特别是在网络带宽资源占用率极高的情况下。本文针对无线网络中参与者的多样性行为,主要包括多样性的通信请求模型、多样性的服务质量要求、多样性的应用传输要求、多样性用户行为下用户体验保证等关键问题给出了一系列的问题模型化和算法研究结果,很好的解决了上述问题,主要研究内容如下:(1)本文研究了满足多样性多播通信的传输调度方案。为了克服现有工作需要假设各个设备的多播通信模型保持一定程度一致的局限性,本文在第二章分析了在各个设备可以任意确定其多播通信中目的节点情况下整个网络的性能表现,以及达到优化网络性能的数据传输调度方案。本文首先提出了一种新的网络模型,该模型允许各个设备在多跳无线网络中在任意区域内选择任意个数不超过节点上限的目的节点,更加符合参与者行为多样性的特点。针对所提出的模型,本文分析了无线网络所能达到的网络容量上界,其中网络容量表示无线网络在一定时长内所能传输的数据总量。在上界的具体分析过程中,本文提出了一种新的指标,用于刻画单节点向其目的节点传输数据时需要面对的资源竞争激烈程度,这一指标能够帮助推导出网络容量的上界。随后,本文扩展一种经典数据传输调度方案,设计出了一种供各节点进行传输的方案,并且通过理论分析证明了这一方案的可达容量下界同网络容量上界是同阶紧凑的,进而证明该方案的优化行。最后,本文讨论并通过实验验证了设备通信模型的多样性对网络总的容量的影响。(2)本文研究了满足服务间隔要求多样性的传输调度方案。为了克服现有数据传输调度方案无法满足一般无线网络中设备存在的不同服务间隔的要求这一现状,本文在第三章研究了如何在满足各个设备不同服务间隔的前提下,同时保证网络资源的充分利用。本文首先提出了一种新的网络模型以及网络稳定性的定义,能够刻画在包含不同服务间隔要求的前提下网络稳定的含义。随后,本文证明了优化的数据传输调度方案设计问题为NP完全问题,进而提出了一种相应的近似数据传输调度策略,该策略综合两种已有的经典方法,在考虑各设备服务间隔的前提下兼顾了网络资源的利用率。本文证明了在一中常见的无线网络模型,即并置网络中,该策略能达到优化的性能,并且进一步分析了不同的服务间隔对网络总体性能及单个设备数据队列长度的影响。最后本文通过实验验证了所提出的策略能够显著的改观各设备间不同服务间隔的保证情况。(3)本文研究了满足不同应用多样性通信请求的数据传输调度方案。为了克服目前的数据传输调度方案大都针对链路级表现进行优化的局限性,本文在第四章研究了如何在考虑到各个应用及其具体运行任务对数据传输存在不同要求的前提下,设计数据传输调度方案。本文首先提出了一种新的网络模型及网络稳定性定义,该模型能够形式化描述各设备上不同应用及任务的通信请求,并且将网络稳定性同一段时间内传输失败的任务个数相联系。具体的,本文提出了一种新的指标,用于刻画在各设备上,属于某应用的一个具体任务在各个时间点的最小数据通信请求。这一指标能够用于表示各个应用的通信请求多样性。而后,本文证明了优化调度策略的设计是一个NP完全问题,提出了一种新的数据传输调度策略,该策略能够根据各个任务对网络资源需求的紧迫程度进行调度,并且保证对网络资源的充分利用。本文随后分析了这一策略的效率性能,并且证明了其在并置网络中可以达到优化的效果。本文同样分析了优化调度策略的设计及证明思路,并且给出了其时间开销。最后,本文通过大量实验验证了所提出的算法能够显著提高各个设备在其各个应用上的数据传输表现。(4)本文研究了包含多样性通信请求下满足用户体验的数据传输调度方案。为了克服现有的数据传输调度方案无法在参与者通信请求存在差异性的情况下平衡用户体验这一局限性,本文在第五章研究了用有限的网络资源服务最大数量的参与者,并且保证各参与者用户体验的问题。本文首先提出了一种改进的网络模型,该模型刻画了不同参与者的不同数据通信请求,并且为各用户提供了一个用户体验的保证。同时,本文提出了一种相应的网络稳定性定义,与一段时间内网络中成功进行数据传输并且满足用户体验要求的参与者数量相关。基于所给出的模型,本文首先分析了优化策略的设计问题是NP完全问题,设计了一个包含两阶段的近似数据传输调度方案,该方案分别确定新到参与者的接入决策和接入点分配,以及针对已接入的参与者的网络资源分配方案。随后,本文分析了这一策略的时间空间复杂度,以及方案所能达到的性能比。最后本文通过模拟实验验证了该方案在确保各个用户服务体验的前提下,能够提高网络所服务的总用户个数。
[Abstract]:With the continuous development of wireless communication technology, the increasing function of mobile devices, and the continuous popularization and application of key technologies such as embedded technology, 3G/4G mobile network, WiFi network, D2D network and other wireless networks have become one of the core channels to support the flow of information in various scenes. Sample participants, such as intelligent equipment holders running different applications, different functional components, control components, and so on. These participants usually have different and complex behavioral purposes while producing large-scale information circulation, and accordingly produce a variety of data communication requirements. A series of new challenges are proposed, including link layer data transmission scheduling, network structure topology design, media access control layer protocol, and application layer resource allocation. The link layer data transfer scheduling scheme is one of the key links in a given network link. On the premise of channel quality, conflict situation and other factors, the equipment for transmission in each time period is determined. More specifically, the link layer data transmission scheduling scheme can allocate the transmission resources reasonably for each participant in different network environment and communication load to guarantee these scenarios, according to the communication requests of each participant. However, the existing system is running properly. However, the existing data transmission scheduling methods are still not perfect. There are still some defects in the main optimization objectives, such as maximizing the network utilization and ensuring the link quality. The main problems are as follows: first, these methods need to ensure the consistency of the participants' behavior to a certain extent and not to the diversity. Second, these methods mainly measure the performance of the whole system from the service obtained by the single link, and can not evaluate the service obtained from the different applications in the scene. At the same time, the corresponding transmission resource allocation scheme to ensure the normal operation of each application is given; and third, taking into account the participation of the system. These methods are often difficult to relate to the user experience of the participants, especially when the occupancy rate of the network bandwidth is very high. This paper focuses on the diversity behavior of the participants in the wireless network, mainly including the diversity of the communication request model, the diversity of the quality of service and diversity. A series of problem modeling and algorithm research results are given in the application of transmission requirements and user experience assurance in diversity user behavior. The main research contents are as follows: (1) this paper studies the transmission scheduling scheme satisfying the diversity multicast communication. In order to overcome the existing work, it is necessary to assume the various assumptions. In the second chapter, the performance of the entire network and the data transmission scheduling scheme to optimize the network performance are analyzed in this paper. In this paper, a new network model is proposed in this paper. The model allows each device to choose a destination node with any number of no more than the upper limit of the node in any area in a multi hop wireless network, which is more consistent with the diversity of participants' behavior. In this paper, the network capacity up to the proposed model is analyzed. The network capacity indicates that the wireless network is certain. In the specific analysis process of the upper bound, this paper presents a new index, which is used to describe the intensity of the resource competition that the single node has to face when it transfers data to its destination node. This index can help to derive the upper bound of the network capacity. Then, this paper extends a classic data transmission. A scheme is designed for the transmission of each node. Through theoretical analysis, it is proved that the upper bound of the capacity of the scheme is the same as the upper bound of the network capacity. Then the optimization of the scheme is proved. Finally, the paper discusses and validates the total network capacity of the diversity of the equipment communication model by the experiment. (2) this paper studies the transmission scheduling scheme that satisfies the diversity of service interval requirements. In order to overcome the current situation that the existing data transmission scheduling scheme can not meet the requirements of the different service intervals of the equipment in the general wireless network, this paper studies how to meet the different service intervals of each device in the third chapter. At the same time, a new network model and the definition of network stability are proposed, which can describe the meaning of network stability under the requirements of different service intervals. Then, this paper proves that the optimal design of data transmission scheduling scheme is a NP complete problem, and then a new problem is proposed. The corresponding approximate data transfer scheduling strategy, which combines two existing classical methods, considers the utilization of network resources on the premise of considering the service interval of each device. This paper proves that the common wireless network model, that is, in the parallel network, can achieve optimization performance and further analyze the difference. The effect of service interval on the overall performance of the network and the length of the data queue of a single device. Finally, this paper proves that the proposed strategy can significantly improve the guarantee of different service intervals between various devices. (3) this paper studies the data transmission scheduling scheme which satisfies the request of different application diversity communications. The previous data transmission scheduling schemes are mostly aimed at the limitation of link level performance optimization. In the fourth chapter, this paper studies how to design a data transfer scheduling scheme on the premise of different requirements for data transmission in each application and its specific operation tasks. This paper first presents a new network model and network stability. Qualitative definition, the model can formally describe the communication requests of different applications and tasks on each device, and connect the number of tasks that fail in the same period of time. In particular, this paper presents a new index to describe a specific task on each device at every time point. The minimum data communication request. This index can be used to represent the diversity of communication requests for each application. Then, this paper proves that the design of the optimal scheduling strategy is a NP complete problem, and proposes a new data transfer scheduling strategy, which can schedule the urgency of the network resource requirements according to each task. This paper then analyzes the efficiency performance of this strategy and proves that it can achieve the optimization effect in the parallel network. This paper also analyzes the design and proof of the optimal scheduling strategy and gives its time overhead. The algorithm can significantly improve the data transmission performance of each device in its various applications. (4) this paper studies the data transmission scheduling scheme which contains the diversity communication request to meet the user experience. In order to overcome the existing data transmission scheduling scheme can not balance the user experience under the presence of the participants' communication requests. In the fifth chapter, in this paper, we study the largest number of participants with limited network resources and guarantee the user experience of each participant. This paper first presents an improved network model, which depicts different participants' different data communication requests, and provides a user experience for each user. At the same time, this paper proposes a corresponding definition of network stability, which is related to the number of participants who successfully carry out data transmission in a period of time and meet the requirements of user experience. Based on the model given, this paper first analyzes the design problem of the optimization strategy is the NP complete problem, and designs a close two phase. Like data transmission scheduling scheme, the scheme determines the access decision and access point allocation of the new participants and the network resource allocation scheme for the participants that have been connected. Then, this paper analyzes the time space complexity of the strategy and the performance ratio that the scheme can achieve. The scheme can improve the total number of users served by the network under the premise of ensuring the experience of each user service.
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TN92

【相似文献】