无线网络与移动计算复习
无线网络与移动计算复习
1-1 概论
有效性问题。频谱资源紧张：日益增长的用户数和有限频谱资源的矛盾。
可靠性问题。信道环境恶劣：用户对业务质量的需求和无线传播环境的矛盾。
香农公式 $C = Blog_2\left(1 + \frac{S}{N}\right)$
无线传输时需要将基带信号转换为中频，再到射频信号，最后通过天线发送。
误码门限：为达到一定误码率需要的最小接受电平门限。
信源编码有效性，信道编码可靠性。
实体，协议和服务：实体表示任何可发送或接受信息的硬件或软件进程。协议是控制两个对等实体进行通信的规则的集合。服务是下层为相邻的上层提供功能调用。
下层的协议对上面的服务用户是透明的。协议是“水平的”，服务是“垂直的”；
网络协议的组成要素：语法，语义，同步
TCP四层结构：应用层、运输层、网络层和网络接口层
OSI七层模型：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层
五层模型：应用层，运输层，网络层，数据链路层，物理层
- 物理层：完成相邻节点间比特流的传输，提供信号调制和无线收发等技术；
- 数据链路层：完成相邻节点之间数据的可靠传输。负责数据成帧，帧检测和媒体访问及差错控制；
- 网络层：完成两个主机之间的报文传输。负责路由生成和路由选择；
- 传输层：在两个主机的不同进程之间提供无差错和有效的数据通信服务。负责数据流的传输控制；
- 应用层：提供访问网络各种接口和应用层协议
1-2 无线个域网局域网城域网广域网
个域网：短距离，低成本，小功耗。蓝牙，红外，射频，UWB，Zigbee；
无线局域网：优点：灵活性，移动性，可伸缩性，经济性； 缺点：可靠性，带宽与系统容量，干扰，安全性；
BSS：无线接入点（Access Point，简称AP）和与之关联的一组无线终端设备（如笔记本电脑、手机等）组成的最小无线局域网（WLAN）单元。
基础架构网络：有AP，Adhoc架构：没有AP；
当多个终端同时访问同一资源时，(如共享的通信信道)，就会产生信息碰撞，这时候就需要多址接入协议。
逻辑链路控制LLC层：提供与网络层的接口逻辑连接，负责流量控制、差错检测和纠正、数据帧的序列化和反序列化等。
介质访问控制MAC层：负责处理物理介质的访问和数据帧的传输，常用的多址接入有无冲突和有冲突两种。
无冲突多址接入：FDMA，TDMA，SDMA，CDMA；
有冲突多址接入：ALOHA接入，CSMA接入，用户数多，接入概率越低，接入时间越长。
随机ALOHA：随时发送—>检测到冲突—>重新发送，不需要时间同步，易损时间2个帧时；
时隙ALOHA：把时间划分为更长的时隙，按时隙发送，需要时间同步，易损时间1个帧时。
带捕获的时隙ALOHA：如果检测到冲突，就接受信号较强的那个分组，信号较弱的分组重发，这样减小的重传的机会。
当呼叫量很大时，平均时延随着呼叫量的增加呈指数关系增长。
CSMA：对ALOHA方式的一种改进，载波侦听多址。用户在发送分组前首先检测信道上是否有载波，如果有载波，则用户等候；一旦检测到信道上没有载波，就立即发送。当然这时还会有碰撞，一旦发生碰撞，仍采取重发的方式，但碰撞概率要小于ALOHA方式。
- 非持续侦听方式（CSMA-NP）：用户有信息发送，就侦听信道，空闲就发送，不空闲就过一会重新侦听
- 持续侦听方式（CSMA-P）：用户一直（持续）侦听信道状态，如果信道空闲，用户又有通信要求，就发送信息包，(还有的是以P的概率发送信息包)
- 侦听检测方式（CSMA-CD）：发送过程中仍然监听信道，有冲突立即停止发送。出现在有线网络中
- 载波侦听CSMA-CA：发送过程中不能监听信道，常用于无线网络中
2-1 网络路由技术
(1)中继器(Repeater)，实现物理层的连接，对信号进行放大整形或再生，以便延长传输距离。
集线器(Hub)-物理层共享
(2)网桥(Bridge) ，提供链路层间的协议转换，在局域网之间存储和转发帧；网桥可以改变帧格式。
交换机（Switch）:数据链路层
(3)路由器 (Router)，作用于网络层，在不同的网络之间存储和转发分组。必要时，用多协议路由器做网络层协议转换。
(4)网关(Gateway)，提供传输层及传输以上各层间的协议转换。
隧道技术：没有协议转换，只有将被传输的数据分组作为中间网络分组承载的数据，穿越过去。
路由器的两个主要功能：选址和转发
路由选路的标准：最小代价，这个代价可能是链路容量，跳数，包丢失率，流的干扰延时。
路由算法的分类：
谁决定路径
- 源路由：源节点决定路由
- 网络路由：网络决定，网络路由包括中心控制(一个路由器计算出所有的路由表)和分布式控制(每个路由器计算自己的路由表)
源节点到目的节点有多少条路径
- 多路径和单路径
使用全局的还是局部的拓扑信息
- 全局：所有路由器有全部的拓扑信息，链路代价信息。(链路状态路由算法)
- 分散式：每个路由器只知道自己的邻居节点和到邻居节点链路的代价(距离向量算法)
是否是适应性算法
- 静态路由和动态路由
Dijkstra算法：
- $C(i，j)$：节点i到j的代价
- $D(v)$：源节点到目标节点v的当前最小代价
- $P(v)$：源节点到目标节点v的当前最小代价路径上的前一节点
- $N$：从源点沿已定义最短路径能到达的节点集合
路由条目：至少由4个部分组成，到哪个网段，从哪个接口出去，到达相邻路由器的哪个接口，路径的开销
静态路由：非直连网段比较少，网络拓扑比较简单；动态路由与之相反
域间内部网关协议IGP：自治系统内部使用的路由协议，RIP，OSPF协议等；
域间外部网关协议EGP：将路由选择信息传递到另一个自治系统中，BGP。
距离向量算法RIP：$d_x\left(y\right)$是从x到y的最小代价路径，路由器的连接状态收到路径上所有节点的影响。
$d_x\left(y\right) = min\left(c\left(x,v\right) + d_v\left(y\right)\right)$，其中v是x的所有邻居节点，有一点像递归遍历的思想，但是不能避免环路，可能无穷计算。(RIP通过从源到目的的最大跳数来防止路由环，使用UDP传送，最大值为15，距离值就是跳数，过于简化)
开放路径优先协议OSPF：每个路由器都维护所在区域的一个全局拓扑数据库，30分钟刷新一次，路由器的连接状态只收相邻路由器影响。当链路状态变化时，泛洪发送与本路由器相邻的所有路由器的链路状态。
OSPF五种消息类型：问候(Hello)，数据库描述(Database Description)，链路状态请求(Link State Request)，链路状态更新(Link State Update)，链路数据确认(Link State ACK)
BGP协议：在AS之间交换”可达性”信息，目的是找到一条能到达目的网络且比较好的路由。每个自治系统至少选择一个路由器作为”BGP发言人”；
网络拥塞：当大量分组进入通信系统，超出了网络的处理能力时，引起网络性能的下降，拥塞时系统性能显著降低
服务质量QoS：可靠性，延迟，抖动，带宽
流量整形：调节进入网络的数据的平均速率，可用漏桶(可能丢失分组)和令牌环桶(不会丢失分组)两种方式。
2-2 线性规划最大流及其解法
网络性能模型：
$K$ 个源目的节点对： $(s_1, t_1), (s_2, t_2), …, (s_K, t_K)$
网络$G = (N, A)$：$N$为节点数，$A$为边界数
$d_k$ : $s_k$到$t_k$需要传输的流量
$u_{ij}$: 边$\left(i, j\right)$对于所有商品的容量限制
$c_{ij}^k$：在边$\left(i, j\right)$上发送一单位k商品流的代价
$x_{ij}^k$：边$\left(i, j\right)$上发送k商品的流量
多商品流的线性规划描述：$Min\sum_{(i,j) \in A}\sum_{k}c_{ij}^kx_{ij}^k$
$x_{ij}^k$代表 $i$ 向 $j$ 供给 $K$ 商品流，$x_{ji}^k$代表 $i$ 从 $j$ 需求 $K$ 商品流，源端只有供给，没有需求；目的端只有需求，没有供给。(记需求为正，供给为负)
一些假定：同质的产品，无拥塞，允许分数流，一对源节点和目的节点。
原问题和对偶问题：
$y_1$和$y_2$相当于为约束条件1式和2式乘的系数。
最大流和最小割定理
最大流问题：确定流的源和宿的情况下，求一个可行流$X$，使$V$最大，$V$是源宿间流的总流量。
最小割理论：一个割是将图的顶点分成两个不相交的子集，并移除连接这两个自己的边的集合。割的容量是值割中被移除的边的权重和，最小割指的是有最小容量的割。
增广路径算法和预流推进算法：都可以得到准确的最大流值
增广路径算法：通过在残余网络（Residual Network）中寻找增广路径来不断增加流量，直到无法找到增广路径为止。残余网络是在已经找到部分流量的情况下，剩余可增加的流量所形成的网络。
定义了$r_{ij}$为$arc(i, j)$ 的残留容量，即$u_{ij}$ - $x_{ij}$，增广路径即为残留网络中s-t的一条路径。
增广路径算法一次只能处理一条增广路径，每一次增广复杂度是$O(N)$， 一种改进的方式就是预留推进算法。
预留推进算法：其专注于对每一条弧的操作和处理，不必一次只处理一条增广路。不满足节点流量守恒，流入的>=流出的；其中流入量>流出量的结点，我们称之为活动结点，算法就是不断地将活动结点，变为非活动结点，使得预流成为可行流。
$e(i)$：节点 $i$ 的盈余；$d(i)$：节点 $i$ 的距离标签；$r_{ij}$：链路的参与容量
预留推进算法每个节点编号：表示在残余网络中该点到 $t$ 的最短路，也称作节点的高度。
算法过程准备，即首先将与 $s$ 相连的边设为满流，并将这时产生的活动结点加入队列 $Q$ 。这是算法的开始。
以后便重复以下过程直到$Q$为空：
(1).选出$Q$的一个活动结点u。并依次判断残量网络$G’$中每条边 $(u, v)$，若$h(u) = h(v) + 1$，则顺着这些边推流，直到$Q$变成非活动结点（不存在多余流量）。(Push推流过程) //同时把所有$v$加入活动结点的队列。
(2).如果$u$还是活动结点。则需要对$u$进行重新标号：$h(u) = min(h(v) + 1)$，其中边$(u,v)$存在于$G’ $中。然后再将$u$加入队列。//后面都满流时就吸不动了，负压自然也要重新计算。
可以证明，通过以上算法得到的结果就是最大流。
显然每次循环后标号和残量网络都是相容的。算法结束时$Q$为空，只可能是没有活动结点。因为一开始就把从源所有的流推了出来，只可能是要么能够推到汇要么最后退回源。显然，一开始源的标号最高，退回源说明源汇之间已被切断，否则总能杀出一条增广路来。
如果该算法的Q是FIFO队列，则时间复杂度为($n^2m$)，/最高标号不会超过$n$（超过时必无到汇的路径），所以$n$个点每个最多重新标号$n$次，两次标号之间$m$条边每条最多推流一次。/如果是优先队列，并且标号最高的点优先的话，我们就得到了最高标号预流推进算法，其时间复杂度仅为$(n^2\sqrt m$，算是比较快的最大流算法了。
2-3 线性规划最大流及其解法
求解最小成本流量分布的问题，它是将最大流问题与每条边上的成本结合起来，以找到在满足容量约束的同时使总成本最小化的流量分布。
3-无线自组织网络Adhoc
应用场景：军事通信，协同计算，应急通信，无线网状网，无线传感器网络；
涉及的问题：移动问题，不需要基础设施问题，组网问题，网络必须快速展开问题。
特点：没有中心实体(如基站)，自组织，自愈的网络；多跳，临时，无中心；
多跳网络的优势：增强了网络扩展性(单跳范围有限)，减少了干扰(如果范围太大，其他设备发送有干扰)，提高了网络吞吐量(通过多跳共享不同的信道，可以同时传数据)，降低了能量消耗(增加设备的发送功率需要成本)；
Adhoc与其他网络的比较：
- WLAN，红外都是单跳网络，不存在路由问题，主要研究点在物理层，终端通过接入点接入网络。
- Adhoc网络是多跳网络，移动终端的通信是对等的，主要关注路由协议为核心的网络层设计；
隐藏终端问题：当节点A向节点B发送数据时，由于阻挡等原因，节点C无法监听到A发出的数据信号，因此节点C认为信道空闲并向节点B发出数据，来自A和C的数据信号在节点B处冲突，造成接收失败。
暴露终端问题：当节点C向节点D发送数据时，节点B同时可以监听到C发出的数据，从而认为信道忙、处于“避让”状态，进而B无法向A发出数据，造成信道浪费；
CSMA(载波侦听多址接入)可以实现信道的随机接入，但是未能解决隐藏终端问题；
CSMA/CA：采用RTS/CTS机制解决了隐藏终端问题；
CSMA/CA的吞吐量：
- DIFS：分布式帧间间隔，数据帧之间的时间间隔；
- SIFS：短帧间间隔，ACK,CTS等短帧的时间间隔
- CW：随机竞争窗口CW时间
网络层影响因素：底层无线通信技术的性能(有限的无线传输带宽)，节点密度， 节点移动速度(拓扑快速变化)，通信负载和通信模式；
主动式路由：DSDV协议：路由表项包括目的节点，到达目的节点的度量值，目的节点相关的序列号；
- 优点：简单，易于实现，能快速对拓扑变化作出反应、
- 缺点：必须维护到所有目的节点的路由信息，路由信息必须定期更新，即使网络拓扑无变化也存在开销，维护的路由可能从不使用。
反应式路由：(按需路由) DSR，源动态路由协议，发送节点在分组中携带到目的节点的路由信息。
- 优点：不需要周期性发送分组来维护全网路由信息，可以提供多条路径
- 缺点：每个分组需要携带完整的路由信息，降低了带宽的利用率；
域路由：不限定域的大小，域内节点通信也可以多跳
分簇路由：有簇首，簇内所有节点与簇首直接通信。
路由的性能指标：端到端的数据吞吐量和数据时延，路由获取时间，乱序交付百分率，效率；
功率消耗：通信有关，计算有关
QoS指标：时延，带宽，分组丢失率，时延变化(抖动)，功率消耗，服务覆盖范围；
4.无线传感网络WSN
定义：无线传感器网络由部署在检测区域内大量的廉价卫星传感器组成，通过无线通信方式形成的一个多跳的自组织网络，目的是协作感知、采集和处理网络覆盖区域中感知的对象信息。
传感器节点组成：传感器模块(信息采集和数据转换)，处理器模块(存储采集的数据和其他节点发来的数据)，无线通信模块(收发采集数据)，能量供应模块(为传感器节点供能)；
三层平台：能量管理平台，移动管理平台，任务管理平台；
数据融合技术：在数据收集过程中，对多个传感器节点收到的数据进行处理和集成，去除冗余信息，以减少网络不必要的能耗；
数据融合的算法：贝叶斯估计，极大似然估计，卡尔曼滤波，最小二乘，聚类分析，神经网络
实现WSN的主要技术：zigbee，WiFi，Bluetooth
- zigbee：专注于低功耗、低成本、低复杂度、低速率的短距离无线网络通信技术；
应用：军事，环境检测，医疗护理，智能家居，建筑物状态监控，空间探索
问题：网络内通信，成本，能量供给，网络结构
5-1 容迟容断网络DTN
现有的网络架构：蜂窝网，有线的骨干网加上无线的最后一跳；
传统的Internet的特点：端到端的路径没有非对称带宽，延时很短，链路损耗很少，节点移动和重组较少，不适合长期存储数据；
DTN产生的背景：随机的节点移动性，大延时低速率，带宽不固定，高错误率低容量，机会性链接，长的排队时延；
DTN的特点：长延时，节点资源有限，间歇性连接，不对称数据传输，低信噪比(高误码率)，可靠性，无ARQ，利用保管传输机制的逐跳可靠性；
DTN架构：运行在已有的网络协议栈上，在应用层上以代理的形式实现，不同网络之间的互操作通过网络边界上的DTN网关实现；需要较低标准的时间同步。
DTN和因特网的比较：
相同点：都是为运行于不同环境的底层协议栈提供互操作，提供存储转发服务；
不同点：DTN使用永久存储器实现消息转发，因特网利用内存实现分组传输；DTN能连接性能差异很大的网络，对于底层协议栈的假设比IP更少，因此比因特网模型更通用。
Bundle束层：
将数据封装为bundle，并为每个bundle分配唯一的标识符，bundle包含了数据本身以及一些元数据，如源地址、目的地址、时间戳等；当节点不能转发时，Bundle层将bundle存储在节点的存储器里。
流量控制和拥塞控制：
- 流量控制：限制向下一跳DTN节点的发送速度。
- 拥塞控制：在DTN网关上处理对永久存储器的竞争。
DTN的特性使拥塞控制很困难：可能很长时间没有下一跳，数据不能排空，而且节点累计的数据还不能删除；
可能的拥塞控制方案：
- 存储空间满时拒绝新的连接
- 将保管传输转移到其他可能的保管节点
- 丢弃非保管传输的消息
- 极端情况下，丢弃保管消息(尽量避免)
DTN中需要命名和编制的节点：主机，路由器，网关
命名机制：每个节点有一个唯一的标识符BID，是唯一用来标识和寻址数据单元的值。
DTN路由：最小化时延，最大化网络吞吐；目的是最大化消息传输成果的可能性，这点和常规路由不同；比如a节点可以转发到b，如果b的交付概率高于a，就会转发；
主动式路由和反应式路由：主动式路由协议可以理解为每个节点试图同步全网拓扑，反应式路由协议可以理解为需要发的时候主动找拓扑，不需要就不找。OLSR是前者的经典例子，AODV是后者的经典例子。前者一般转发速度快，但拓扑维护开销大，且在高动态场景性能差，后者则反之。
按照对拓扑知识的了解分类：没有知识，完全知识，部分知识；对拓扑知识了解的越多，算法越复杂，算法的性能性能表现就越好；
DTN网络的描述：可以用图来抽象描述，边在延迟，容量和方向性方面是时变的，当一条边有零容量时，说明断连；
6-移动计算
相比分布式计算的区别：网络质量不可预测，节点信任度低，本地资源有限，电池消耗限制；
移动互联网：用户通过手机等手持终端以无线的方式接入网络；
应用：办公，医疗，移动支付，通信社交