【作者】 李卓；

【导师】 陆桑璐； 陈道蓄；

【作者基本信息】 南京大学 ， 计算机软件与理论， 2012， 博士

【摘要】 移动互联网是通过移动网络进行接入的互联网,它是移动通信同互联网的融合。近年来已成为工业界、学术界研究的热点之一。随着移动互联网访问需求的不断增加,传统移动网络的接入、传输能力面临重大挑战。为应对这一挑战,一方面,出现了各种新的支持用户接入的网络结构,比如Femtocell网络(飞蜂网)等；另一方面,在接入技术发展的同时,新型的移动网络传输模式被提出,比如机会传输等。Femtocell网络技术的引入,改善了传统蜂窝网络接入中数据传输速率低、能量利用效率低等问题。机会传输模式的引入,使得数据传输可通过节点间“存储-携带-转发”方式进行,降低了骨干网络负载,提升了服务能力。在Femtocell网络中,不同用户同基站间的通信相互影响。为达到全局网络性能的优化,我们研究了用户关联基站的选择、信道分配及功率控制。进一步地,在无Femtocell基站覆盖的区域,我们考虑了机会传输。网络中仅需要部分节点直接接入因特网,其余节点经由它们获得数据,这些节点被称为移动无线网络同因特网间的网关。为使用户快速获取数据,我们对网关选择方法进行研究,以期从所选网关开始,广播数据报文所需要的期望时间最短。当网关节点从因特网获取到数据之后,它们通过机会传输方式进行共享。特别地,在移动用户感兴趣的因特网数据中,视频文件等大数据(Bulk Data)是其中重要组成部分,我们研究了针对大数据如何设计端到端传输机制,以达到高吞吐量。最后,针对混合传输模式并存的移动无线网络(对于两个用户而言,他们既可通过接入点、Femtocell基站等经由骨干网络通信,亦可以机会传输方式通信),我们分析了容量、时延等传输性能如何随节点数量而演化。本文主要贡献可以概括为以下个方面：(1)针对基于Femtocell接入的通信资源分配,我们以最大化最小蜂窝吞吐量为目标,研究了其中的用户-基站关联、信道分配、功率控制问题。在基站功率连续可调的场景中,我们将其建模为一类非凸的混合整型非线性问题(Non-convex Mixed Integer Non-linear Problem, MINLP),证明了信道分配及用户关联都是NP-Complete的,特别的,当可分配信道数目大于等于3时,对信道分配问题,当且仅当NP=P时存在近似比大于等于1的多项式时间复杂度近似算法。类似的,对用户关联问题,证明了当且仅当NP=P时存在近似比大于1小于2的多项式时间复杂度近似算法。为解决此问题,我们提出一种基于轮循优化思想的算法,迭代地对用户关联、信道分配和功率控制进行优化。在设备功率离散可调的场景中,我们研究了当用户、基站关联关系确定时信道、功率分配问题。基于粒子群优化,我们提出了一种新的分配算法PCASO,其中,为产生新的粒子,定义了三个操作：变异、局部交叉和全局交叉。实验显示,PCASO极大地提升了网络的性能。(2)针对移动无线网络同因特网互联的网关选择问题,我们证明其为#P难,并提出了四种启发式算法：Random, MCS, CBS和FT。基于生成函数理论,我们对Random算法的性能进行了理论分析,其对应的广播时延可近似作为MCS、CBS和FT算法结果的上界。通过模拟实验,我们对四种算法性能进行了比较,其中当网络节点数为30时,FT算法对应平均时延低于Random算法15%；当网络节点数为40,…,50时,CBS算法对应平均时延低于Random算法10%。(3)针对移动无线网络中的大数据传输,我们引入了无反馈的分段网络编码机制。首先,基于节点间通信机会的概率分布,利用微分方程对目的端的数据接收过程进行建模,并给出了其在一段时间内成功接收K个编码报文概率的闭解。基于此,我们对端到端数据传输的最大持续吞吐量进行了分析,给出了其上限的闭解表达,并分析了达到此上限的必要条件。进一步的,我们设计了一种基于分段网络编码的传输机制,模拟实验表明,实验结果同理论分析相吻合,同时,所提出的传输机制也逼近于理论上的最优值。(4)针对有骨干网络支持的移动无线网络,我们对其容量、平均报文时延等传输性能指标进行了分析。讨论了独立同分布、固定速率的随机游走、列维飞行三类模型。对独立同分布、固定速率为(?)(1/√n)的随机游走模型,我们给出当容量为(?)(1)、(?)(1/√n)时的平均报文时延,其中,n为网络节点数目。证明当网络容量的上限为时,平均报文时延可达最优,其中,K为骨干网接入点数目。对三类模型,求得了平均报文时延同容量间的比率,分析了同固定混合无线网络相比的关键平均时延；我们的工作为该类型网络传输性能分析提供了理论支持。更多还原

【Abstract】 In mobile Internet, users connects the Internet through mobile devices they carry. It is the convergence of mobile communication and Internet. In recent years, it has be-come the hot topic in both the industrial and academic areas. As the applications on mobile Internet grow, the traditional wireless access and transmission mode through cellular networks has to be improved. Femtocell networks have been introduced and the users can enjoy higher data transmission rate. In addition, this type of networks benefits the operators because the power efficiency of the femtocell base stations will be higher than the marco base stations. Since it is beneficial for users and operators, special attention for developing femtocell solutions has been received recently from a lot of researchers. Besides the development of wireless access method, a new transmis-sion mode based on the contact between two mobile users has been proposed. Due to the lack of continuously connected paths between every pair of nodes, communication usually adopts the "store-carry-and-forward" manner. Because opportunistic transmis-sion is usually through Wi-Fi or Bluetooth devices, it’s free of charge and generates no traffic on the cellular infrastructure network. Thus, it can decrease the overhead and improve the service quality.In Femtocell networks, communication between different base stations and users may interfere with each other. To optimize the performance, the macrocell and all in-volved different femtocells need to allocate the communication resources to a group of users cooperatively, such as power and channels. We investigate the resource allocation problem in femtocell networks. For opportunistic transmission, some nodes are chosen as gateways to connect with the Internet via cellular networks. We address the problem of choosing suitable gateways from all the nodes to reduce traffic overhead and delay of information access in mobile wireless networks. After the gateways get data from the Internet, they can deliver it to others. Because a large proportion of the data which the users are interested in is bulk data, we study how to design transmission protocols with high throughput for it. For all pairs of source and destination, there are two dif-ferent transmission modes. One is without the help of gateways, which is similar with opportunistic transmission. The other is through gateways, which is like the traditional infrastructure based transmission. We investigate the trade-offs between delay and ca-pacity in mobile wireless networks with infrastructure support. In this paper, the main contributions are as follows.(1) For the resource allocation in femtocell networks, we target at maximizing the minimal throughput among the cells. We discuss two different cases. When the power can be adjusted continuously, a joint optimization over power control, channel allocation and user association is considered and the problem is then formulated as a non-convex mixed integer non-linear problem (MINLP). For the sub-problem of channel allocation and user association, we prove they are both NP-complete. Furthermore, we prove that when the number of channels is equal or larger than3, there is no polynomial-time algorithm with approximation ra-tio ρ≥1for the channel allocation problem unless NP=P. Similarly, we also prove that there is no polynomial-time algorithm with approximation ra-tio1≤ρ<2for the user association problem unless NP=P. To solve this problem, we proposed an alternating optimization based algorithm, which applies branch-and-bound and simulated annealing in solving sub-problems at each optimization step. When there are different discrete levels for the power to set, a joint optimization problem over power control and channel allocation is formulated. We propose a particle swarm optimization based algorithm PCASO, in which we define three operations for generating a new particle, such as mu-tation, local crossover and global crossover. We demonstrate the efficiency of PCASO by numerical experiments.(2) For gateway selection in mobile wireless networks, we formulate it as K-GW Selection problem, where K nodes are selected as gateways to distribute data in order to minimize the expected broadcast delay. We prove that the problem is#P-hard. To solve it, we propose four heuristic algorithms, namely Random, MCS (Monte Carlo-based gateway Selection), CBS (Centrality Based gateway Selection), and FT (Frequent Trajectory based gateway selection). Based on generating function, we propose a theoretical method for the calculation of the expected broadcast delay in Random. Intuitively, the delay can be regarded as an upper bound for that in MCS, CBS and FT. Through simulations, we compare the performance of the four algorithms. It is found that FT outperforms Random by about15%when the network size n=30. The algorithm CBS outperforms Random by10%when n=40,...,100.(3) For bulk data transmission in mobile wireless networks, we introduce feedback-less segmented network coding. Based on the knowledge of the contact rate among nodes, we model the data reception process at the destination using dif-ferential equation, and calculate the probability that it can receive K coded pack-ets successfully during a period of time in closed-form. To our best knowledge, we are the first to derive the upper bound of the maximum sustained throughput in a closed-form when feedbackless segmented network coding is involved. We provide two necessary conditions, i.e., the intra-segment coding condition and the inter-segment scheduling condition, for achieving this optimal performance. Based on the understanding of these conditions, we then propose a practical SNC protocol that approaches the theoretical bound asymptotically. The segment de-lay of the proposed protocol is also analyzed. Correctness of our theoretical analysis is verified through simulations. Also, the experiment results prove the effectiveness our proposed protocol.(4) For the trade-offs between capacity and average packet delay in mobile wireless networks with infrastructure support, we consider two synthetic models I.I.D mo-bility model, random walk mobility model with constant speed and Levy flight mobility model which is based on human mobility. For I.I.D mobility model and random walk mobility model with constant speed (?)(-/(?)n), we give theoretical results of the average packet delay when capacity is (?)(1),(?)(1/(?)) individually. n is the number of nodes in the network. It is proved that capacity is bounded above by; when the average packet delay is optimized. K is the number of gateways in the network. The bounds of the average packet delay divided by capacity under the three models are established, as well as the criti-cal average delay for the capacity comparing with that in static hybrid wireless networks. Our work provides useful theoretical insights on the performance of mobile wireless networks with infrastructure support, and will help the schedul- ing and routing protocol design.更多还原