基于tinyos的无线传感器网络路由协议的研究与实现【4】
孔庆云 董湘麟
第四章：动态扩展路由协议的详细设计与实现
上一章讲述了动态扩展路由协议的总体情况，把动态扩展路由协议分成了前端和后端，并介绍了它的运作方式。本章将从多个方面更详细的介绍它的具体设计与实现方法，主要从协议的算法本身架构上讲述，尽量避开那些和平台紧密相关的方面。
前面说过无线传感器网络节点硬件功能非常有限，这也给运行其上的软件从复杂度和尺寸上加了限制。为了尽量压缩代码尺寸，简化计算，路由协议在实现时把功能分成模块实现，尽量发挥代码的效率，协议里一些必要的计算尽量用移位操作来实现，简化计算，提高运算效率。
本章主要从消息、接口、路由表、邻居列表以及选路算法等几个方面进行描述。
§4.1消息类型
在动态可扩展路由协议的实现中，使用了多种消息类型，这些消
息间采取层了层嵌套的形式。比如：控制消息嵌套在基本消息的数据域里，选路消息又嵌套在控制消息的数据域里。从外层看，在无线传感器网络里传播的都是基本消息类型，和其他已实现的路由协议没有任何不同，用于控制路由的控制信息和节点间通告邻居列表信息的选路信息都封装于基本信息的数据域中。这种包装方式，保证了消息类型的一致性，便于同种类型路由协议间的替换。
4．1．1 基本消息
tinyos中最基本的消息类型是TOS_Msg，其它类型的消息都是被封装在这个消息里面。TOS_Msg主要包含如下这些域：
目的地址(addr)：用于确定接收节点。
消息类型(type)：用于辨别网络中不同种类的消息。
组号(group)：无线传感器网络通过组号把整个网络分成一个个网格，同组间的节点才可以相互通信。由于该路由程序应用于一个小型网络，通常是在一个网格内进行，节点都被设置在一个组内。
消息长度(length)：其值表示的是字节的个数，这个长度指该消息包中所携带的数据的长度。
循环冗余验证(crc)：对整个消息进行循环冗余计算得到，计算过程主要由硬件或系统提供，用于保证数据的完整。
数据(data[])：用于存放数据，里面也可以嵌套其它的消息类型，比如一些路由的控制信息等。
以上这些域是实际发送时发送的内容，另外TOS_Msg还定义了一些并不参与实际发送过程，但是与辨别发送过程的成败、发送接收的同步相关的几个域也在这里进行了定义。其中与本文所讲算法有密切关系的一个域是：
显式的确认（ack）：由接收方收到信息后发送给发送方，发送节点在发送完消息后并不立刻返回，而是要监听信道一段时间，等待接收方返回这个ack ，ack为1表示消息被成功接收了，本次发送成功；若ack为0则表示消息没有被接收到，本次发送失败。根据ack的值可以判定发送的成功与否。
TOS_Msg是最基本的消息类型，通信信道上出现的消息都是以这种消息形式传输的。同时，它也是其它消息类型的载体，其它的消息一般都是封装在它的数据域中。
4．1．2 控制消息
控制消息嵌套在TOS_Msg的数据域中，主要对增加一些对路由情况的控制。它主要包含一下这些域：
源地址(sourceaddr)：发送该消息的节点地址
根地址(originaddr)：最初发送该消息的节点地址
序列号(seqno)：该消息的序列号，用于统计是否有包丢失
路径数(paths )：该消息传输所占用的路径数（从第一个扩展节点算起）。
扩展地址(extaddr)：对该消息进行路径扩展的节点
跳数(hopcount)：从扩展节点到汇聚节点的跳数（消息从一个节点传输到另一个节点称为一跳）。
数据(data[])：要传输的数据，数据域的最大长度是TOS_Msg数据域的长度减去控制消息包头这些参数所占长度之差。
控制信息用于对选路进行控制，嵌套于TOS_Msg的数据域中，而洪泛消息、选路消息又嵌套在控制消息的数据域中。无线传感器网络中的节点根据控制消息携带的控制信息进行本地路由表、邻居列表的更新。
4．1．3选路消息
为了简化程序，控制代码的尺寸，洪泛消息和路由选择消息使用同一种格式的消息包。选路消息主要包含如下这些域：
当前父节点(parent)：也称作当前转发节点，由于从数据源开始，信息传输的路径是以树（非严格意义上的）的形式进行的，起始于根节点，收敛于汇聚节点，每个下一跳节点都成为该节点的父节点。
路径花费(cost)：当前节点至汇聚节点的路径花费，由连接费用和转发节点连接数共同决定。
连接数(links)：当前节点的连接数。
邻居节点信息计数(NeiborCounter)：选路消息所携带的数据域中包含的邻居节点信息的条数。
数据：里面放的是邻居列表的部分信息，主要是邻居节点的ID号和对应的接收率（ReceiveRate），它的长度由邻居节点计数确定。
选路消息用于节点间交换邻居列表信息，以便更新节点间的连接费用等信息，为选择转发节点提供依据。选路信息以广播的形式进行发送，接收到选路消息的节点检索其中的信息，更新本地邻居列表的发送质量等数据以便用来计算和每个节点的连接费用。
连接费用的评估算法是：记录从邻居列表中每个节点成功接收到的数据包的个数（利用每个数据包所携带的序列号）、丢失的包的个数，根据这两项数据计算出接收率（ReceiveRate），然后把邻居列表中部分节点的接收率放入选路消息中广播出去。其他节点收到选路消息后检索其中的是否有对应自己接收率的记录，若有则用这个接收率值更新发送质量（SendQuality），发送质量又会随着邻居列表的更新指数级递减。根据接收率和发送质量计算出连接费用（LinkCost）。计算公式为：
LinkCost ＝ K/(ReceiveRate × SendQuality)
K为比例常数。最后，根据连接费用和当前节点的连接数（CurrentLinks）计算出该节点到汇聚节点的路径费用。
§4.2 接口
程序中提供的接口定义尽量和tinyos系统中的接口保持一致，这样有利于路由程序间的替换，当应用程序需要更换路由协议时可以很方便的只做少量变化就可以了。整个路由程序提供给应用层的主要接口有：发送接口，接收接口，截取接口和路由控制接口。
其中发送接口是这些接口中最重要的一个，在路由前端提供，它负责为应用层提交的消息进行选择路径并发送。当应用层采集好数据并且准备发送时，调用路由前端发送接口，发送接口通过调用内部选路接口运行路由后端选路算法，为应用层提交的消息填充上转发节点地址以及一些路由控制信息，然后再通过动态消息模块调用mac层发送机制发送。
接收接口虽然也在前端提供，但是它一般不直接应用于应用层，应用层直接使用动态消息模块提供的接收接口，这里接收接口的主要功能是根据收到的数据包所携带的路由信息进行选路转发。在接收接口中要调用截取接口，对所接收的消息中的数据进行一些数据融合等方面的计算以提取更有效的数据，减少通信流量。数据融合不是本文关心的问题，截取接口的实现采用的是缺省的默认实现，只是预留出这个接口供以后有数据融合等需求的用户使用。
路由控制接口用于路由前端和后端交互以及应用程序和路由程序的交互，这个接口中提供了很多命令供查询当前节点的路由信息，可以实时得到当前节点的选路信息，为应用层选择发送时机提供信息。
路由协议内部调用的接口主要是选路接口，选路接口在路由后端实现，在路由前端的发送和接收接口中调用。它的功能是：给定一个准备发送的带有数据的消息，为它选择路径，填充好消息头部的转发地址和路由控制信息。选路接口的功能体现了路由协议最本质的功能，也是本文路由协议实现中最核心的部分，它的实现在会在选路算法中着重描述。
§4.3 路由表、邻居列表
路由表和邻居列表都以记录的形式提供查询，路由表的维护建立在
邻居列表维护的基础之上，因为路由表的维护需要查询邻居列表中记录的转发节点的信息。
路由表维护的是路径信息，供选路算法查询，用于选路和控制多条
路径不相交等操作。
邻居列表维护的主要是一些跟通信信道状态密切相关的参数，这些参数用于判定当前信道状态以及一个邻居节点是否可以作为转发节点而选入转发节点集（FCS），也有一些参数用于避免出现通信环路。
4．3．1 路由表的建立
路由表的每个记录包含如下信息：
根地址(originaddr)：消息的起始节点地址。
源地址(sourceaddr)：发送该消息的节点地址。
转发节点地址(nextaddr)：要把该消息发往的下一跳节点地址。
路径数(paths)：该消息占据的路径数。
有效标识(active)：标识该记录是否有效。
路由表在路由后端文件中定义。当节点启动时，在初始化函数中进行初始化。当有新路径时，在路由表中找一个无效的表项并记录下来这条路径。增加新路径还必须考虑扩展路径时的情况，扩展只对第一条扩展路径进行记录，因为决定一条路径的有三点：根节点、源节点和目的节点，而对于扩展的多条路径这三项是相同的，所以只需记录一条就可以了。
4．3．2 路由表的维护
路由表中的记录随着通信信道的变化也会动态的变化，如果路由表记录的下一跳节点或者源节点失效，则要删除这个表项，此时这条路径已经失效，不再是一条完整的路径。对路由表的更新是放到时钟任务中进行的，每隔一定时间（若干个定时器时间），时钟触发一次硬件中断，在中断处理函数中提交时钟任务（Timertask（）），在时钟任务中调用各种表的更新函数（updateTable()），而在这个函数中再提交路由表更新函数对路由表进行更新。更新时，通过查询邻居列表中记录的转发节点的信息，判断转发节点是否有效，若无效则直接删除这条路径。需要注意的一点就是对于路由表项的更新必须是原子操作，也就是说修改一个路由表项的时候不可以被其他的线程中断掉，不然路由表项的记录就不能真实反映路径情况，甚至是错误的。
Tinyos系统中的硬件触发事件很多，而且大部分是无法预料的，硬件事件可以中断比它优先级低的线程，而任务不可以中断其它任务，以FIFO的形式进行调度，在路由表的更新或建立过程中把操作语句放入atomic关键字中就可以做到操作路由表项的过程不被打断。
4．3．3 邻居列表的建立
邻居列表的记录主要包含如下信息：
邻居节点地址(id)：用于标识每个邻居节点的地址。
当前父节点(parent)：记录邻居节点的当前转发节点地址。
路径花费(cost)：该邻居节点至汇聚节点的路径花费。
孩子标志(childLiveliness)：用于标识该邻居节点是否为本地节点的一个孩子，孩子节点不可以选为转发节点也就是父节点，避免出现环路。
连接数(links)：该邻居节点有多少个连接分支，也就是说有多少个节点选择它为父节点。
丢失消息数(missed)：该邻居节点丢失的消息的个数。
收到的消息数(received)：该邻居节点收到消息的个数，丢失的消息数和收到的消息数用于计算节点的接收率(receiveRate)。
上一个消息包的序列号(lastSeqno)：通过上个消息报的序列号与现在收到的消息的序列号之差来计算丢失消息的数量。
记录状态标识(flags)：用于标识该记录是否有效、新建还是已建，记录的后两个状态用于计算节点间的链路质量过程。
活性值(liveliness)：用于标识该节点的记录信息更新的频度。
至汇聚节点的跳数(hop)：用于控制选路算法选择用户节点集（CS）中节点的限度。
接收率(receiveRate): 和发送质量一起确定连接花费。
发送质量(sendQuality)：和接收率一起确定连接花费。
邻居列表也是在路由协议后端文件中定义的，在节点启动时初始化。
当发现新的邻居节点时，从邻居列表中找一条空记录来记录，若没有空记录，则从记录中找出一个发送质量最差的邻居节点记录用作记录新节点信息。
4．3．4 邻居列表的维护
邻居列表的更新大体上分成两部分进行，一部分在接收接口和截取接口中更新；另一部分放到时钟任务中进行，在时钟任务的更新函数（updateTable()）中调用邻居列表更新函数。
更新函数更新的依据是：在邻居列表的每条记录中，部分信息项之间有依赖关系。比如，接收率是通过处理丢失的消息数和收到的消息数得到的。利用邻居列表每条记录中信息项的依赖关系，邻居列表更新函数对部分信息项进行处理，得到其他信息项的值。而邻居列表更新函数要处理的这些信息项的值是在接收接口和截取接口中更新的。
在接收接口和截取接口中更新邻居列表主要是从收到的消息中提取邻居节点信息，用提取的这些信息更新邻居列表中对应节点的记录。收到的消息又分为普通数据消息和选路消息，普通数据消息和选路消息都包含发送节点的部分信息，比如发送序号、根节点地址等等，当接收接口或截取接口接收到消息后，从中提取这些信息更新邻居列表中对应记录的信息项。选路消息除了和普通数据消息共有的那些节点信息外还包含额外的一些邻居列表信息，用于更新邻居列表中那些需要节点间交换信息才能确定的信息项。邻居列表的更新速度比路由表快很多，因为链路状态的变化对它记录的各种参数的影响要远超过路由表，对路由表的维护建立在对邻居列表维护的基础之上。
邻居列表在路由协议的实现中处于极为重要的地位，它记录了能和本地节点直接通信的所有节点的详细信息。路由表、转发节点集（FCS）和用户集（CS）等数据结构的生成或维护都需要查询邻居列表信息，邻居列表信息也是选路算法选路的重要依据。
§4.4路由算法实现
路由算法的实现分别体现在路由程序的时钟任务、选路接口、发送
接口和接收接口中， 下面对实现中核心部分进行具体描述。
4．4．1 洪泛过程
在节点启动时，调用初始化接口对路由所使用的各种数据结构和模块进行初始化，把除汇聚节点外所有节点的路由锁状态置为锁定状态，汇聚节点的路由锁一直处于开锁状态。汇聚节点开始广播洪泛消息（没有包含邻居列表的选路消息），网络中的收到消息的节点解开路由锁，并根据消息中携带的源结点跳数信息对邻居节点划分FCS集和CS集，继续广播洪泛消息。随着邻居列表中的填充，网络中的节点开始广播选路消息，洪泛过程逐渐结束。
4．4．2 转发节点（父节点）的选取
转发节点的选取是放到时钟任务中进行，每个一定时钟周期，对邻居列表或FCS集进行检查，从中找出符合条件的转发节点插入FCS集的队头。算法如下：
1．检查本地节点是否为汇聚节点，若是则返回。
2．检查FCS集是否为空，若为空，确定要查找的目标集合为邻居列表；若不为空，则确定要查找的目标集合为FCS集。
3．从目标集合中取出一个没有访问过的节点。
4．如果该节点存在如下情况，返回3。
I. 不存在该邻居节点。
II. 该节点的当前转发节点是本地节点。
III. 该节点当前没有转发节点。
IV. 该节点的跳数为无穷大。
V. 该节点至汇聚节点的路径花费为无穷大。
VI. 该节点的发送质量或接收质量低于最低要求值。
VII. 该节点是本地节点的孩子节点
5．计算到该节点的连接费用和路径花费，如果连接费用低于要求值，返回3。
6．如果该节点是当前的转发节点，更新它的路径花费，返回3。
7．比较该节点与目标集合中上一个节点的路径花费，若比其小，把该节点插入FCS队列队头；若比其大，返回3，目标集合中第一个节点的上一个节点的路径花费为无穷大。
FCS集用一个队列表示，队头指定的节点为最佳转发节点，以次
次之。选择转发节点时，从FCS队列队头开始，以次选取，这样选取的节点就是目前最好的几个转发节点。每隔一定时钟周期，转发节点选取算法运行一次，保证FCS集中记录的转发节点的次序能及时反映当前信道的情况。
4．4．3 动态扩展路径
路径扩展分为两种情况，一是当发送数据时，一条消息发送失败次数超过最大允许值，为它扩展路径，另一种情况，当接收到一条反馈消息时，根据反馈消息扩展路径。动态扩展路径算法分为两部分描述，分别从发送失败和接收到反馈消息两种情况进行说明。
I 发送失败时：
1.检查消息中由Mac层返回的ack值，若ack为1，转12。
2．消息是否是被广播出去的，若是，转12。
3．本地节点是否为汇聚节点，若是，转12。
4．消息被重发的次数是否达到最大限制值，若是，转6；不是转5。
5．消息的重发计数加1，运行选路算法，为该消息重新选择转发节点，重新发送，转12。
6．该消息是否为反馈消息，若是，转12；不是，转7。
7．如果该消息目前只占有一条路径，转10，否则转8。
8．比较本地节点到汇聚节点的跳数与到扩展节点的跳数，若大于，转10，否则转11。
9．该消息占用路径数加1后是否大于最多允许的路径数，若是，转11；不是，转10。
10．为该消息增加一条路径，消息中标记本地为扩展节点，更新其中扩展节点的跳数为本地节点的跳数，根据消息占用的路径数选择转发节点发送。同时，消息的重发计数清零，转12。
11．把该消息标为反馈消息，按其源路径返回给扩展节点，转12。
12．退出。
II．接收到反馈消息时：
1．该消息的扩展节点是否为本地节点。若是，转2，否则，选择路径转发该消息，退出。
2．该消息所占用的路径数加1是否超过最多路径允许值，若超过，退出；没有超过，转3。
3．把该消息占用的路径数加1，选择转发节点发送，退出。
以上算法在发送接口和接收接口中实现，当节点准备好数据要发送时，把数据放入消息中提交给路由层的发送接口，在发送接口中调用选路接口为消息选择转发节点，如果发送失败调则用上面提到的算法I。当接收到消息后，检查它是否为反馈消息，若不是，调用选路接口为其选择转发节点发送，若是，则调用算法II。
4．4．4 选路算法
选路算法主要在选路接口中实现，选路接口放在路由后端实现，前端调用。每当要发送数据时，都要运行它选择转发节点，为要发送的消息填写好消息的头部。选路算法处于本路由协议实现的核心位置，只要节点要发送消息，就必须用它来选择转发节点，因此，调用选路接口的地方很多，贯穿于整个路由算法。
每当有选路要求时，提交给选路接口要发送的消息，运行如下选路算法：
1．查找路由表，检查是否存在该消息的路径（根据消息携带的根结点信息）。若不存在，转8。
2．检查该消息是否为反馈消息。若是，当前转发节点取路由表中记录的源节点，转12。
3．检查路由表中记录的转发节点（下一跳节点）是否为有效转发节点。若否，转8。
4．检查该消息是否为因发送失败而重发的消息。若是，转8。
5．检查该消息占用的路径为单路径还是多路径。若为单路径，当前转发节点取路由表中记录的转发节点，转11。
6．检查该消息的源地址与路由表中记录的源地址是否相同。若不同，转返回选路失败。
7．检查该消息的扩展地址是否为本地节点。若否，当前转发节点取路由表中记录的转发节点，转11。
8．根据选路接口中携带的FCS队列的下标信息，从FCS队列中取出一个转发节点，指定它为当前转发节点。若FCS队列为空，返回选路失败。
9．检查路由表中是否记录了该消息的传输路径。若没有记录，在路由表中查看是否有空记录，若有空记录则记录下这条路径。
10．检查本地节点至汇聚节点的跳数与该消息源节点的跳数之差是否大于允许的最大可逆向传播的最大值（反馈消息除外）。若是返回选路失败。
11．为该消息填写转发地址、序列号等头部信息。填写消息头信息时，还有如下处理：若本地节点是扩展节点，维持消息中记录的跳数信息不变，否则使用本地记录的跳数信息。
12．返回选路成功。
EE直播间
更多
-
无线前沿新技术与测试技术峰会-线上直播 直播时间： 12月05日 09:30 -
首场直播发布： Keysight AP5000 系列新型高性价比模拟信号源 直播时间： 12月06日 10:00 -
全面掌握功率表应用及校准 直播时间： 12月10日 10:00 -
提升毫米波信号测试精度 直播时间： 12月18日 14:00
关闭
站长推荐
/2 
/2
文章评论（0条评论）
登录后参与讨论