Architecture and Evaluation of an Unplanned 802.11b Mesh Network

Architecture and Evaluation of an
Unplanned 802.11b Mesh Network
《无计划的802.11b Mesh网络的架构和评价》

目录
1主要观点和解决的问题 2
2关键技术 2
2.1：架构设计 2
2.2Roofnet 设计 2
2.3评估 4
2.4NETWORK USE 14
3 论文的主要贡献 15
4思考 15

















1主要观点和解决的问题
这篇论文主要是对无线Mesh协议802.11b的性能水平进行评价，该协议在提供高性能的无线接入的同时，仅需很少的部署计划和操作管理。该协议的架构主要包括无计划节点位置（而不是已经计划好的拓扑结构）、全方位的定向天线（而不是定向链接）和多跳路由（而不是单跳基站）。该协议能满足无线网络对于易部署的需求，然而这需要承担网络性能降低的风险。
本文的实验场景是37个散布在四平方公里的节点，经实验证明，即使没有经过计划部署，该网络能够为用户提供672kbits/s的网络速率，而且这是在平均路由长度有三跳取得的。
本文对该协议的架构的多方面进行评价：节点密度对连接性和吞吐量的影响；路由协议选择的特点；在全方位的定向天线下高速连接Mesh对鲁棒性和吞吐量的作用；单跳节点作为Roofnet节点的潜在性能。
2关键技术
2.1：架构设计
本协议实现的架构设计包含以下四类：
(1)约束节点的位置，而不是一个已经计划好覆盖范围和性能的拓扑结构；
(2)全方位天线，而不是高质量链接的定向天线；
(3)多跳路由，而不是单跳基站或者接入点；
(4)优化路由提高吞吐量，而不是修复整个移动网网络路由。
然而真正实现起来却不得不面对网络性能下降的风险，如：无线范围太短、许多连接质量低、节点间相互影响而导致持续丢包等。
本文主要使用Roofnet来对无计划Mesh网络802.11b架构进行评价，与前人专注于Roofnet物理层的研究不同，本文研究的是Roofnet的端到端特性。
2.2Roofnet 设计
Roofnet是部署在一个方圆4公里的区域，分布在剑桥、曼彻斯特。志愿者在高楼上配置屋顶式天线，这样产生的节点没有真正的随机但也没有特别的计划。
（1）主要硬件配置有：每个节点主要有PC、802.11b网卡、屋顶式全方位天线。
（2）主要软件配置有：每个节点主要有密钥交换、DHCP服务器路由软件、可监控网络状态的web服务器。每个节点通过DHCP自动配置用户电脑，然后将该节点作为一个默认IP路由器。具体的软件配置包括：
寻址：Roofnet有自己的格式的报头和路由协议来加载IP包信息，在Roofnet层每个Roofnet节点有独特的地址，这与IP层的IP地址类似。每个Roofnet节点也必须通过DHCP来分配IP地址，节点利用NAT转化以太网和Roofnet的数据包。
网关和互联网接入：Roofnet设计假设有一小部分的志愿者愿意分享他们的有线互联网接入。，整个网络中除了固定的gateway来提 供Internet接入外，还可以有些临时的gateway（比如一台电脑除了无线网络，自己还有一个以太网接口连在Internet上）。这篇文章给出 了具体利用这些gateway的方法：每台机器启动后，先以DHCP client的身份找Internet，如果找到了，那自己就可以做一个临时的gateway，如果找不到，就转换回DHCP server，给别的节点提供接入。
（3）主要的路由协议为：
Roofnet采用Srcr协议作为其路由协议，用于找出节点之间高吞吐量的路由线路。虽然全方位天线给出了很多连接点，但是很多连接质量都很低，因此Srcr需要通过评估每隔连接点的连接吞吐量。
具体做法是：每个Srcr节点维持一个该节点到其他节点度量的数据库，然后利用Dijkstra算法进行路由选择。新接入节点通过发送DSR类型的洪泛查询，然后将所有节点的回馈信息存入数据库。洪泛查询容易引发的问题是路由结果并非最佳路由。
（4）路由度量
Srcr利用ETT(“estimated transmission time”)作为路由的度量，ETT是通过估测数据包以连接点最大吞吐量传输速率的时间来进行路由度量。Srcr选择具有最低的ETT路线，因为这条路线很可能在单位时间内发送最多的数据包。
ETT度量指的是每个路由之间ETT之和，其中每个路由器之间的吞吐量 和路由器端到端吞吐量关系式:

（5）比特率选择
Roofnet选择802.11b传输比特率为1，2，5.5，11兆比特/秒，而且丢包率为40%的单跳路由实际上比完整的双跳路由（只有50%）能够发送更多的数据。Roofnet的算法称为SampleRate。用于调整发送数据报在链路上的比特率。SampleRate的决策来自实际数据传输，而不是周期广播探测。这样能使得其能调整的选择更快和更准确。
2.3评估
本节主要讲述了Roofnet端到端性能和架构选择的影响。评估结果显示：在对吞吐量的基本测量结果是平均吞吐量是627kbits/sec，平均时延是39毫秒。网关之间的平均传输速率为1395kbits/sec，平均时延22毫秒。
本次评估分七大部分来进行。首先是 Roofnet 端到端的性能的特点和选择这个体系的一些影响。第二部分介绍了在这个网络之上的吞吐量和反应时间的基本测量。第三部分研究如何充分利用大量的链路提供给全向天线。第四部分通过对评价不同大小的子网节点，解释了节点密度在连接性能和吞吐量上的影响。第五部分Roofnet如何利用高度相连的网格。第六部分比较了多跳路由和单跳路由类似于接入点网络的体系结构。第七部分主要是介绍的方法指出了多条路由的吞吐量的一个主要限制因素是跳间相互冲突。
2.3.1方法
以下是四类Roofnet测量方法：
（1）多跳的TCP的数据集：在每对Roofnet节点间进行15秒的单向大量的TCP传输，吞吐量结果和路由循环的ping时间在传输结束时记录在路由器上。在测量多跳TCP时可发现约10％的节点对没有找到工作路由。
(2)单跳的TCP数据集：通过每对节点的直接无线传输链路测量TCP吞吐量
(3)丢失矩阵数据集：指的是每队节点在每个802.11b传输率下使用1500比特广播的丢失率。
(4)多跳密度数据集：测量在一个固定的四个节点间多跳TCP的吞吐量。
2.3.2基本性能

图2给出的在Roofnet的一对节点之间的TCP吞吐量的分布。中间值为400kb/s，平均为627。

表1指出随着节点对的跳数数目增加，每个节点对的平均TCP吞吐量减少和反应时间增加。

表2指出了多跳为丢失的情况下不同比特率的理论最大吞吐量。
表1和表2指出Roofnet的单跳路由操作在平均传输速度是保持在5.5兆位，但对于长路由会有不相称的减缓。

表3指出了自选网关的每个节点（并非跳数计算安排）TCP吞吐量。
2.3.3距离和链路质量
文中给出了每个可用的链路的吞吐量和距离间的分布图。大部分可用的链路距离长度在500至1300米，最好比特率是500kb/s。在几百米的链路的传输比特率达到2兆比特/秒。

在对Srcr的吞吐量和链路距离的分布图，可看出Srcr所用的大部分所有链路速度比2兆比特/秒还要快。此外从图表中得出Srcr有效的支持几百米的短距离的链路，忽视了大量的可能携在一跳一公里或者更长的带数据的链路。所以快速短跳就是最好的策略。

图4指出Srcr通过SampleRate协议得出的链路发送CDF的可能性，可以看到在0.8时，差不多有四分之一的链路丢包率已经超过了50%。
2.3.4 密度的影响
我们知道，网状网络在节点密度相当高才是显著的。
从图5可以看到模拟不同大小的Roofnet子网检测密度的效果，可以得出随着节点数的增加连接节点对的分数，平均吞吐量和平均跳数都在增加。一个密集的网络提供一个更广泛的高质量的短链路，即使他们因此导致了跳数的增加。


2.3.5Mesh鲁棒性
目前测量网状网络的健壮性最即时的方法是每个节点所拥有的潜在有用的邻居节点数目。如果一个节点只能通过它的邻居节点来路由，那么这个邻居节点的值就是可疑的。当一些节点只通过一个或两个邻居节点进行路由行为时，节点的大部分会利用更多的邻居节点。这样，Roofnet在通常的路由中能充分利用网状体系结构。邻居节点如图6所示，该节点传输概率在40%以上。

图7显示了每个节点在寻找到其他链路的路由时作为独立的第一跳的邻居节点数目的直方图。

而图8显示了对平均吞吐量有贡献的几个最好的环节，但是需要指出的是，有10几个最好的链路需要将吞吐量降至一半。

图9显示了累计的最佳连接的节点数目对于吞吐量的影响。

2.3.6Architectural Alternatives
评价Roofnet的架构的一种方法是，将Roofnet与另外一种单跳网络相比，该单跳网络的每个节点间都必须通过直接无线传输链路和网关通信，而不是通过多跳路由。因此在单跳网络中网关的数量和位置很重要，要求网关要离每个节点都近。以下是Roofnet与单跳网络的对比
(1)最优选择
表4给出的数据表明在一个单跳架构下，5个网关就可以覆盖所有的Roofnet的节点。对于任意给定的网关，多条转发提供更高效的吞吐量。多跳在吞吐量上的优势是由于它使用高质量的短链路序列，而不是单一的低质量的长链路。

(2)任意选择
作者给出了在不同数量的随意选择网关的性能。如果Roofnet是一个单跳网络，则需要25个网关覆盖所有的节点。大约90%的节点是被10个网关覆盖的，但有少数的节点很难被覆盖到。从表5对比得出仔细的网关选择增加了多跳和单跳路由的吞吐量。对于5个或者更少的网关，随机的选择多跳网关和仔细选择单跳网关相比能提供更好的性能。但是对于数量很多网关来说，仔细地选择单跳网关比随机选择多跳网关要更好些。

2.3.7跳间冲突
表1指出在单跳网络平均速率是251kbits/sec，因此恶意估计两跳网络的流量应该减半，即为1225kbits/sec，然而，实际的数据确实771kbits/sec。图10指出期望得到的单跳路由吞吐量不同于实际测量的值。相比较测量的多跳吞吐量几乎比预期的低很多。作者给出为何链路结合比单独要慢得原因是同时一个路由的不同跳数发生的传输有冲突导致了数据报的丢失。The 802.11 RTS/CTS机时所期望的能够阻止这些冲突，但是却没有提高性能。没有做到阻止冲突的发生。
2.4NETWORK USE
作者在对这个Roofnet的应用后，通过采集所监测的4个Roofnet网关中一个在Roofnet和以太网之间转发的数据报，作者分析出：
在一个24小时内，网关转发平均速率为160kb/s，94%为网关收发的无线流量，5%为协议控制数据报的流量。48%数据量是从网关的一跳的一个节点的出入数据量。36%为两跳的，剩下的大约16%是转发超过三跳或更多的网关。
时间的分析上来看。作者统计了24小时内网关最忙的59374秒，包括了分组和重传记录，分组和重传发送和传输，网关传输时间等，但是不包括帧之间间隔和退回帧的时间。这就意味着网关的无线70%监听时段是繁忙的。大部分的网路带宽的消耗，是因为使用了 BT和peer-to-peer的文件共享程序，约占整个数据传输量的30%。大部分剩下的流量是短连接对无特定端口的。虽然网页请求占用了少量的数据传输，但是作者也指出：68%的通过网关的连接是网页链接，只有3%是BT。
3 论文的主要贡献
目前针对无线Mesh网络的研究方向主要有以下几种：
1、集中在为了在静态网状网络增大吞吐量评估路由的测量。
2、主要研究面对移动性的路由修复。
3、研究链路层802.11的行为，以便指导高层协议的设计。
而本文以独特的视角研究了如何评价一个由活动用户部署而成的Mesh网络，重点研究其架构选择所带来的影响而不是设计协议本身。
通过评估作者指出，基于Roofnet的屋顶式802.11bMesh网络具有良好的性能。该网络架构利用全方位天线和自动配置软件和多跳路由，大大简化了部署的难度。
评估指出Roofnet节点间的平均吞吐量在627kb/，仅用几个英特网网关就能够给实际网络提供服务，网关的位置也可以很方便的确定。对比假设的单跳网络，Roofnet的多跳网状在连通性和吞吐量上面都有提高。
4思考
本文的应用场景虽然说没有经过特定的计划，但是覆盖面不广，用户随机性也不够，我觉得这对实验的结果应该会造成一定的影响。