基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第15页
由于传感器节点的资源有限，网络中的节点数目也十分庞大，要求每个传感器节点都能有足够的存储空间来存储一张巨大的路由表是不现实的。因此，在传感器网络中，往往是按需路由和混合路由比较受到青睐。
（2）按节点参与通信方式的划分
根据节点参与通信的方式，路由协议可以分为以下几类：
①. 直接通信型协议：传感器节点直接发送数据给接收节点，在这种网络中，
如果网络规模较大，节点的能量很快耗光。另外随着节点数目的增加，网络中的数据冲突将变的更加严重。
②. 洪泛式路由协议：它是一种古老的协议，不需要维护网络的拓扑结
构和路由计算，接受到信息的节点以广播形式转发数据包给所有的邻节点。洪泛式路由的实现比较简单，但容易带来信息的“爆炸”和“交叠”，而且它没有考虑能源方面的限制，具有“资源盲区”的缺点。
③. 平坦路由协议：网络中的所有节点都是平等对待的，当一个节点需要发
送数据的时候，可能通过其它的节点为中转节点进行转发，最后到达接收节点，这种路由方式叫做“多跳”。通常来说，在接受节点附近的节点参与数据中转的概率要比远离接收节点的节点参与的概率高。因此，接收节点附近的节点由于过于频繁的参与数据中转，会较快耗光能量，这对于能量有限的无线传感器网络来说，是一个很大的问题。
④. 层次式路由协议：基本思想是将传感器节点分成不同的簇，簇内收集的
监控信息都交给簇首，簇首可以通过数据融合减少传输信息量，最后簇首把处理后的数据传送给终端节点。相比前面的路由协议，层次型路由协议具有以下优点：能满足传感器网络的可扩展性；有效的减小传感器节点的能量消耗，从而延长网络生命周期。
（3）按路由发现过程的划分
根据路由的发现过程，可以分为以数据为中心的路由协议和以位置信息为中心的路由协议。以位置信息为中心的路由协议，它利用节点的位置信息，把查询或者数据转发给需要的地域，从而缩减数据的传送范围。实际上许多传感器网络的路由协议都假设节点的位置信息为已知，所以可以方便的利用节点的位置信息将节点分为不同的域。基于域进行数据传送能缩减传送范围、减少中间节点能耗，从而延长网络的生命周期。
以数据为中心的路由协议，它提出对传感器网络中的数据用特定的描述方式命名，数据传送基于数据查询并依赖数据命名，所有的数据通信都限制在局部范围内。这种方式的通信不再依赖特定的节点，而是依赖于网络中的数据，从而减少了网络中大量传送的重复冗余数据，降低了不必要的开销，从而延长网络生命周期。
由于业务需要，无线传感器网络也需满足QoS带宽等需求。所以无线传感器网络的QoS路由得到广泛的研究，主要方法有遗传算法[33]、蚁群算法[34]等。
5.3 基于量子遗传算法的无线传感器网络QoS路由选择方案
5.3.1 系统模型
本文假设：①节点初始能量充分且规格指标均相同；②仅因传感节点能量耗
尽失效导致网络拓扑变化；③节点能进行简单的冗余数据处理；④节点只接收一跳之内的相邻节点发送的数据；⑤网络中传感器节点已知自己的地理位置信息。为了便于描述，需要对本方案运行的网络、所使用的能量模型及节点选择模型分别进行说明。 
① 网络模型
无线传感器网络是由包括目标、传感器节点和汇聚节点组成，在研究当中往往将其抽象为赋权有向图 。V表示网络节点的有限集合，E表示节点间的链路集合，边的权代表无线传感器网络中的某种度量。
QoS路由是在图G中寻找满足业务QoS约束并且从源节点S到目的节点D的可能路径 。本论文主要考虑带宽和成本约束，则设定QoS参数为：
瓶颈带宽： ；
成本： ；
无线传感器网络QoS路由发现问题可定义为寻找从S到D的可达路由p应满足条件：
常量B、C分别为连接请求所要求的带宽、代价约束。
② 能量模型
在无线传感器网络中如果频繁使用一些节点构成的路径传输数据，容易使这些节点因能量消耗过快而过早失效，从而使整个网络分割成互不相连的孤立部分，减少整个网络的生存期。
在无线传感器网络中，能量主要消耗在分组的收发过程中。本文使用W.R.Heinzelman等人提出的能量模型[35]计算节点的剩余能量。在该模型中，如果节点i向节点j发送k位数据，那么节点i消耗的能量为：
                            (5-3)
其中，Eelec= 50nj/bit，εamp= 100pj/bit/m2，d是节点i到节点j的距离。在该方案中，由于每个节点只与其邻居节点通信，并且总是以与节点的通信范围对应的能量级别发送数据，因此，d等于节点的通信范围dr。
节点j消耗的能量为： (5-4)
这样，每个接收并转发数据的中间节点i消耗的能量为：
                              (5-5)
从而，节点i的剩余能量ERi可定义为：
ERi = ERi–Ei                                     (5-6)
显然，节点的剩余能量在0和Emax之间，Emax是节点的初始能量。在网络部署之初，所有节点的剩余能量相同，均为Emax。需要说明的是，不同的应用对节点的最小剩余能量有不同的要求，不一定总是0，为了方便描述，用Emin表示节点剩余能量的下限。如果一个节点的剩余能量小于应用所要求的Emin，该节点就成为不可用节点。在无线传感器网络正常工作期间，每个可用节点应根据其自身的行为，及时更新其剩余能量，并向其邻居节点作周期性的报告。如果一个节点在两个连续的周期内都没有收到其某个邻居节点的报告，就认为该邻居不可用，并将其从邻居节点列表中删除。
在一条已构造的链路p上传输的数据总量为 时，链路p上节点能量消耗函数Costp为：
                  (5-7)
式（5-7）中，n表示链路p包含的节点数,dij为链路p相邻两节点（一跳）之间的直线距离。
③ 节点选择模型
汇聚节点接受指令后，广播ADV信息，ADV信息至少包含汇聚节点的节点位置域 和这次任务所需带宽的最小值Brequired等字段。然后，汇聚节点开始计时，在实验中，计时时间为2s。各个传感器节点接收到ADV信息后，将自身所剩带宽Bleft与Brequired比较，若Bleft≥Brequired，则建立自己的邻居表；若Bleft≤Brequired，则丢弃此ADV信息且节点恢复到原状态。
定义5.1 (可用邻居集合) 节点的邻居节点中满足QoS带宽需求（Bleft≥Brequired）的节点集合为节点i的可用邻居集合，标记为
 。
假设节点i满足节点选择机制的要求，则节点i将建立自己的邻居表。节点i广播HELLO信息，HELLO信息包含节点i的地址信息 和自身的剩余能 。可用节点集合 中的节点j接收到节点i的HELLO信息后，发送ACK信息回馈节
点i，ACK信息同样包含节点j的地址域 和自身的剩余能 。节点i接收到节点j的ACK信息后，将节点j填入到自己的邻居表；若未接收到节点j的ACK信息，表示节点i的下一跳邻居不会是节点j。然后，可用节点将发送REQ信息(REQ信息包括节点位置域 字段)至汇聚节点，申请参与此次任务；若汇聚节点在计时期(2s)内接收到此信息，则此节点将有权参与此次任务，最终汇聚节点将持有参与此次任务的可用节点集合。

 << 上一页  [11] [12] [13] [14] [15] [16] [17] [18] 下一页