本文是一篇计算机论文，本文对共享单车车联网的网络层进行了深入的研究，从基于共享单车的应用场景开始，然后提出了适用于共享单车的网络结构并进行分簇路由算法的研究，最后考虑到数据传输的多样性以及单车数量的庞大，采用SDN网络作为上层数据传输的网络架构并研究合适的路由算法。随着科学技术的不断发展，共享单车作为人们短距离出行的首选方案，因此它有着很好的发展前景。
第一章绪论
1.1研究背景与意义
城市的快速发展与社会生产力和科学技术的进步密切相关[1]。为了促进城市的长期高效可持续的发展，1987年世界卫生组织（World Health Organization,WHO）在Healthy Cities的项目中首次提出了智慧城市的概念[2,3]。智能交通系统（Intelligent Traffic System,ITS）作为智慧城市交通中关键的一环，提高了交通的可操作性和安全性，有效降低了环境污染。如今，共享单车作为一种较为方便的出行方式，已经遍及城市各处。从2016年开始，中国的共享单车行业高速发展，六个月内崛起了20多家企业。一些数据显示，共享单车的用户已达到100万[4]。因此，它为促进经济发展特别是共享经济创造了巨大的利益[5,6]。但是随着单车用户的不断增加，一些问题也不断出现，比如乱停乱放、车辆损毁比较严重、分布不均等。据报道，一些城市中存在很严重的单车破坏现象，使得单车修理率达39％[7]。因此，在部分人眼中，共享单车成为了“城市垃圾”，毫无用处。但实际上，共享单车的价值尚未完全开发和利用。通过对共享单车相关知识进行学习和分析，总结出它具有以下四个特点。
（1）数量庞大：一些统计数据表明，中国已经放置了多达1000万辆共享单车。到2017年12月为止，中国共享单车客户可达2.21亿，仅在半年内增加了1.15亿用户，其增长率达到108.1％[8]。
（2）分布广泛：共享单车多数分布在校园、地铁站各个出口、公交车站旁边、居民区楼下、商业区和公共服务区。观察Mobike和哈啰单车在城市中的分布情况，可以发现单车几乎遍布在街道、社区、地铁站等各个角落。
（3）智能化：近年来，共享单车蓬勃发展并逐渐智能化。比如使用二维码就可以轻松解锁共享单车而不再需要输入密码。目前，智能锁基本上由几种类型的模块组成，例如控制、通信、感应、执行和电源。
（4）热点区域的高密度：根据高峰单车起点到终点的汇总统计，可以观察到单车的分布与人们的社交网络密切相关[9]。
1.2国内外研究现状
1.2.1关于共享单车车联网的相关研究
共享单车作为智能交通系统的一种特例，因其价格便宜、骑行距离短和骑行方便而备受欢迎，回溯其源头为20世纪60年代，图1.1简述了其发展历程。根据它的发展历程可以发现，新一代的共享单车配备了部分传感器模块，使其能够实现GPS定位、扫码开锁等功能，更加便利了人们的生活。
在文献[10]中最先提出了共享单车车联网（Internet of Shared Bicycle,IoSB）的概念，并将IoSB与无线通信、定位、信号感知、供电和数据分析等技术结合去探索共享单车的作用。作者将IoSB架构分为五层，并分别展示了每层所实现的功能，如图1.2所示。作者提到在IoSB中应该包含多种技术，不仅能实现传感器数据采集，还能进行数据挖掘和分析，并进行数据通信。此外，作者针对不同的技术进行分析并提出适合的应用场景。根据文献[10]提出的网络结构，文献[11]将边缘计算技术引入其中并创建了超轻量边缘计算算法来优化扩展坞的使用，使得单车的分布更有意义。
第二章相关背景知识介绍
2.1遗传算法概述
在本文所研究的路由算法中，均是以遗传算法为基础进行研究。由于在本文中采用分簇多跳的方式，所以簇首需要寻找一条合适的路径将数据经过多个簇首的转发来传送到基站。这个寻路径的过程就采用遗传算法来实现。
2.1.1遗传算法基本概念
本文所研究的路由算法均是使用遗传算法进行最优路径的寻找，因此在本节中对遗传算法的相关内容进行详细介绍。
（1）基本概念
遗传算法（Genetic Algorithm）是通过模仿自然界中生物遗传和进化机制成立的一种搜索算法[29]。通常，有约束和无约束的复杂问题能够通过遗传算法得到解决。遗传算法主要用于机器学习和问题优化，优化是使某些东西比其他技术更好的技术。在优化中，我们可以提供了一些输入集，然后根据输入得到输出。
（2）基本思想
遗传算法进行搜索的开端是随机产生的群体，这个过程也成为种群初始化。群体中产生的每一个个体都可以看做是问题的解决方案（称为“染色体”）。每一轮产生的群体通过适应性函数计算其适应度值，然后根据适应度值进行选择。按照自然界适者生存的规则指明，适应程度的高低与被选中的高低呈现正相关关系。
2.2 SDN网络概述
SDN是由Mckeown教授在2009年正式提出[30]。SDN不是一种具体的网络，而是一种新型网络架构，将控制平面与数据平面分离，并且可被编程，大大提高了网络的灵活性。它通过解耦控制器来实现允许网络管理员通过抽象底层功能来管理网络服务，控制器通过将流量转发到所选目标的基本设备来决定如何路由流量[31-33]。传统的网络结构由固定的网络设备和在网络设备上部署的网络协议来组成网络。如果对网络有新的需求，一般都要重新部署设备及其网络协议，这使网络设备的网络控制功能与数据转发之间产生很强的耦合关系，所以如果网络想要扩展以及软件升级将会耗费更多资源。
2.2.1 SDN网络架构
一般来讲，SDN网络架构主要分为三个部分，分别是应用层，控制层和转发层，如图2.3所示。应用层和控制层构成控制平面。应用层主要实现SDN的各种网络应用，比如实现负载均衡和防火墙等功能。控制层最核心的组成部分为SDN的控制器，通过南北方协议为上下层提供服务。控制层对基础网络设施进行管理是通过南向接口OpenFlow协议来进行的，而应用层的可编程性由北方接口提供。控制层可以进行数据平面的统一管理，例如进行拓扑管理和下发流表等功能。
与传统网络结构相比，SDN网络最重要的特点就是控制平面和具体的网络设备解耦。控制平面在解耦后形成大脑对变化的业务层需求进行适配和编排，再用不同的方式下发完成设备的转发。在一个路由过程中需要完成三项任务，分别是建立拓扑、传递不同的节点的路由信息、根据不同需求计算出源节点到目的节点的路径。从这三点来看，SDN因为天然有全网视图，能够知晓各个节点的信息，所以比传统路由协议有优势。
第三章基于遗传算法的分簇多跳路由算法研究......................21
3.1算法的描述..................................21
3.1.1算法的提出及设计描述....................................21
3.1.2关于选举簇头的研究.............................22
第四章基于遗传算法的SDN路由算法研究...............................34
4.1基于SDN的网络体系结构.........................................34
4.2路由算法的设计和实现..................................................35
第五章总结与展望...................................51
5.1总结................................51
5.2展望....................................52
第四章基于遗传算法的SDN路由算法研究
4.1基于SDN的网络体系结构
在前面第二章中提出了基于IoSB的分簇的网络结构并拟采用智能路灯作为固定节点，在第三章中对分簇的路由算法进行了研究。本章将SDN网络引入IoSB，研究SDN的路由算法为共享单车车联网上层网络之间进行数据转发。在图4.1中展示了SDN网络结合IoSB的网络体系结构。整个体系结构分为六层，分别是IoSB体系结构、SDN无线节点、SDN无线接入基础设施、SDN数据平面、SDN控制平面和SDN应用平面。
在整个结构中，SDN无线节点是从SDN无线访问基础结构发送和接收消息的智能路灯，它们在逻辑上由SDN控制器管理。在数据平面中，包含访问点（AP）和基站（BS）的SDN无线访问基础结构被抽象为SDN的交换网络。在控制平面中，SDN控制器用于感知整个网络的总体状态，并做出控制整个数据转发的决策。SDN控制器负责全局策略，包括身份验证和移动性/流量管理，而控制器定义的策略则在数据平面上实现。数据平面和控制平面的分离提供了整个服务区域的全局视图，在该区域中可以使用可编程应用程序以实现全局功能。最后一层为分簇的IoSB网络结构，由簇头将数据发送给SDN无线节点，进行数据的采集与转发。
第五章总结与展望
5.1总结
本文主要针对共享单车车联网的网络层进行研究，论文主要介绍一些关于共享单车的应用研究并根据IoSB提出未来的应用场景、基于遗传算法的分簇多跳路由算法以及基于遗传算法的SDN路由算法三部分。
首先，在本文中提出了一种适用于共享单车的网络结构，并在不同的应用场景下对单车进行分析，基于此提出了不同情况下共享单车未来的应用场景。接着对遗传算法进行介绍，包括它的思想，基本原理和实现的基本步骤，并讲述了遗传算法实现的理论基础。最后对SDN网络相关知识进行了基本的介绍，包括SDN的网络架构，采用SDN网络架构的好处，SDN网络的关键技术--OpenFlow，涵盖了控制器、交换机和OpenFlow协议。
其次，在基于遗传算法的分簇多跳路由算法部分主要介绍了分簇多跳路由算法的提出、实现以及性能分析。在算法提出中主要介绍了算法的设计原由和簇首的选举，基于单车移动的特性加入了随机速度这个因素。接着针对遗传算法的每一步进行了详细描述来实现最优路径的实现。
最后在Matlab仿真实验中，将经典的LEACH算法和CECA算法与本文中提出的算法进行比较，发现在相同的条件下能延缓节点死亡过程，进而提升网络性能。最后，在基于遗传算法的SDN路由算法研究部分主要介绍了共享单车基于SDN的网络体系结构、路由算法的设计和实现、仿真环境的配置以及结果分析。提出的整体网络结构分为六层，SDN网络作为共享单车数据传输的上层网络。路由算法的实现分为了链路管理和路由决策两个部分，分别描述了控制器和交换机之间进行交互来进行网络状态信息的获取，构建拓扑结构感知链路以及使用遗传算法进行路径选择。接着介绍了进行仿真实验的Mininet软件和Ryu控制器，并对基于跳数的最短路径、基于时延的最短路径和基于带宽的最优路径进行仿真实验。最后对本文提出的算法进行仿真并进行结果分析，在大规模网络中实现端到端数据传输时，基于遗传算法的路由算法相较于其他三种算法有更小的时延。
参考文献（略）