杨诚，詹永照

基于Ad Hoc 网络通信协定协议研究

杨诚，詹永照

Ad Hoc网络的关键技术是路由技术，对网络整体性能产生着最重要的影响，针对Ad Hoc网络动态变化的拓扑结构，原有固定网络中的路由协议已经能满足其需要，要求必须对新的Ad Hoc路由协议进行设计。基于Ad Hoc网络的基本概念，以双线性对和层次路由协议为基础，提出ad hoc网络中通信有效的密钥协定协议，对应逻辑密钥协定模型与实际网络拓扑结构，使建立和动态更新初始群密钥得到了支持，具有较小的通信量。实验和性能分析后得知，针对有较大的范围、较强的设备处理能力，而较差的通信环境而言，提出的协议效果非常好。

Ad hoc 网络；密钥协定；层次路由；双线性对

0 引言

为了使有线网络对人们的束缚得以摆脱，渴望自由通信能够随时随地进行，我国最近几年开始大力发展无线网络通信[1]。移动中的通信能够借助便携计算机或个人数字助理（配有无线接口）来实现[2]。不过只有在有线基础设施（如基站）的支持下方能实现移动通信[3]。基于将通信带进没有固定基站的地方，出现了Ad Hoc网络技术。网络节点移动性很强是Ad hoc网络的特点，存在非常脆弱的成员关系与无线链路，所以必须重视安全通信[4]。一般来说，安全的密钥是保证网络安全的重要手段，所以就要重视对会话密钥的安全进行研究[5]。不过针对实际的应用，通常这些协议都会分离密钥协定模型与实际的网络拓扑结构，从而其有效性与安全性就有可能出现问题，也就不太适合ad hoc网络[6]。

要提高ad hoc网络中密钥协定协议的效率，就要使通信量得以降低，方法有二：（1）基于对ad hoc网络层次路由（Hierarchy Routing）技术的运用，分簇处理网络，达到基本一致的密钥分配逻辑结构和实际网络拓扑结构，密钥树的相邻结点尽量选用实际网络中的相邻点，从而使单播问题得以最大程度的避免，使单播问题带来的不稳定性和复杂性得以削弱，从根本上使协议的通信复杂度得以降低。（2）基于对双线性映射额利用，再改进RSTR(改进的STR)协议，进一步降低其通信量，从而在具有较大范围、较强节点处理能力并在较大网络延迟的环境中适用，像军事与紧急救助等场合。

1 Ad Hoc网络的一般加密算法

在应用了各种类型的加密算法后，从而有可能实现认证性、完整性、安全性与机密性，对称加密算法、单向Hash函数、非对称加密算法与数字签名是主要的几种加密算法。

（1）对称加密算法

针对密钥的使用，发送者与接收者都一样，从而说明双方对信息的加密与解密都可以使用这一密钥。相对简单、较短的密钥长度是对称加密算法的特点，所以，可以快速运算，对产生极大消耗的CPU资源进行加密操作，对大数据量的信息进行加密，对称加密算法是非常适用的，有助于对信息安全提供极大的保护。不过换言之，因为二者需要在协商的基础上对一个秘密密钥进行共享使用，从而二者其一就有可能会泄露密钥。

同时，若相互通信的人有n个，就会有n-1个秘密密钥保存在每个人手中，则需要对n*（n-1）/2的密钥数目进行管理，管理这么多的密钥有一定的难度，同时，怎样向相应的信息获取者安全地传递密钥也是一大难题。DES、AES、CAS、3DES、IDEA与CAST等是比较流行的对称加密算法。

（2）非对称加密算法

在加密明文时，采用的密钥是一对，而且各不相同，包括个人私有的私钥和对外公开的公钥。二者性质非常特殊，也就是只有用对应的公钥才能解开私钥加密的密文，私钥不具备解密的功能，反过来也是这个道理。

一些很难解决的数学问题决定了非对称加密算法的安全性，诸如对两个大素数的乘积进行分解、对离散对数问题求解、对椭圆离散对数问题求解等，以现有的计算机水平来解决这些难题，即便将公钥得到也没有办法将相应的私钥推出。在非对称加密算法性质良好的基础上，从而在网络安全系统中得到了广泛的应用。不过由于其具有较长的密钥和很慢的运算速度，所以，只是在较小数据量的情况下比较适用。

同时，伪装攻击容易光顾非对称加密算法，也就是中间人（man in the Middle）攻击：若密钥交换正在A与B之间进行，这时介入交换的是第三个人C，初始的公共值本由A向B发送，这时C进行了拦截，进而另一个公共值由C发送到B，然后C又拦截了B发给A的消息，但是B却不知道这一切，从而一个共享密钥的协议在A与C之间达成，并且另一个共享密钥的协议在B与C之间达成，所以，A到B的消息就被C在中间拦截了，进而对A与C共享的密钥解密进行操作，对消息内容进行修改，接着基于对B与C共享密钥的使用，向B进行转发；相反的，B发给A的消息过程也被C篡改，但是A与B并不知情。RSA、EIGamal、Diffie-Hellman与Ecc等是比较流行的非对称加密算法。

（3）Hash函数

用某一固定长度“消息摘要”（Message Digest）对任意长度的消息进行压缩需要借助Hash函数，不同于对称加密算法与非对称加密算法，逆向运算是Hash函数做不到的，密钥也不需要。无法进行逆向运算就是Hash函数安全性的所在，也就是单向的算法，“摘要”能够被用户从原文得到，但是，原文却无法从“摘要”得到，所以，以“摘要”作为信息就能够安全的在网上传送。除此之外，消息原文不一样，被同一个Hash函数运算后，也会得到不同的结果，所以Hash函数有助于完整性检验。MD5与SHA等是比较流行的Hash函数。

（4）数字签名—数字签名（Digital signature）

作为一个加密的消息摘要，在一个文档后面附加的数字签名—数字签名，基于非对称加密算法与Hash函数的组合完成了对它的建立，能够在发送者身份与文档完整性的确认中使用。消息内容的机密性并不能得到数字签名的保证，不过有时，对消息来源进行证明要重要于隐藏消息的内容。有些时候，消息的认证性与完整性是需要的，机密性却不需要，就像路由更新信息在网络上传递的时候，加密是并不需要的，不过是否可信的路由更新的来源是需要确认的。此处我们再举一个例子来说么消息来源认证的重要性，针对电子商务与银行事务，必须重视并认真对事务的来源进行确认，是对任何事务采取行动前必须要做的。RSA数字签名算法与数字签名标准DSS是最常用的一些数字签名算法。NIST提出了基于非对称加密算法的DSS。

相比RSA，针对密钥的生成，DSS具有更快的速度，二者性能基本相同，不过具有很慢的签名验证速度。当前阶段，针对最终用户或设备认证的建立，非对称加密技术往往是许多安全系统的首选，公钥的分发要遵循某种安全的方式，就像借助数字证书，数字签名的创建采用Hash函数，同时，证书内数据的完整性必须确保。一般通过某种加密算法来保证数据的机密性。对数据与业务流量机密性进行提供的同时，也可以部分或全部地用于其它安全机制的实现，在网络安全中最重要的部分就是密码技术。

2 CEKAP协议设计

以单跳原则为基础，CEKAP协议分簇网络都能通过单跳到达簇中的任意节点。借鉴文献[1]，文章利用两个过程对密钥进行协定：建立初始群密钥与构造逻辑群密钥树，通过IKA（Initial Key Agreement）过程完成；加入与移除初始群密钥建立后的网络节点等事件，通过AKA（Auxiliary Key Agreement）来完成。网络逻辑结构体现为逻辑群密钥树，不一定完全对应网络的物理结构，群密钥树的构造基于IKA过程对分簇信息的利用。

2.1 参数设置和逻辑密钥树

假定加法群表示为G1，乘法群表示为G2，素数q是二者的阶，G1的生成元表示为P，双线性映射用ê：G1×G2→G2表示，Hash函数用H：G2→Z表示，能在Z中映射G2上的元素。CEKAP协议的逻辑群密钥树如图1所示：

图1 CEKAP协议的逻辑密钥树

群密钥树由簇密钥树与主干密钥树组成。簇密钥树用虚线椭圆标出，叶子节点表示实际网络节点，以小圆表示，簇头是实心圆，添加的虚拟节点用于建树表示为空心方形。各个簇密钥树由主干密钥树连接，实心方框表示其节点，节点也是虚拟的。

因为网络节点与叶子节点相对应，为了方便叙述，文章用一个概念表示二者。全部节点编号采用三元组〈c, l, v〉，节点所属簇号表示为c；在簇c中从底向上节点所处层号表示为；节点在c簇l层按照从左至右的顺序的顺序号表示为v，1为簇密钥树中 c、 l、v取值的开始，c=0（主干密钥树中）。如A的编号为〈1, 1, 1〉，B的编号为〈6, 2, 3〉。c簇 l层的全部节点表示为〈c, l, *〉，一层的代理表示层中v最大的节点，用S〈c, l 〉表示；c簇的全部节点表示为〈c, *, *〉，这一簇的代理表示为簇中〈c, l-1, *〉层的代理，用S〈c, l 〉表示。该层与下层密钥的更新由层代理负责，簇的密钥的更新由簇代理负责。

簇密钥树中的虚拟节点表示为〈c, l, 1〉（l〉1），在l层〈c, l-1, *〉层的代理的提升是其实际。主干密钥树中的虚拟节点表示我〈0, l, 1〉，在主干密钥树中所辖的最后一个簇的代理的提升是其实际。c簇第l层的节点数（含内部节点）表示为#(c, l )，{1, 2, 3}为其取值。每一随机秘密值r〈c, l, v〉都会对应一个叶子节点。c簇l层以下全部叶子节点协定的密钥值表示为k〈c, l〉，公开给这些叶子节点，不过保密于其它节点。c簇全部节点协定的簇密钥表示为kc，公开给c簇，保密于其它簇。

最终的群密钥用K表示，kc以至K的值都可以通过每个叶子节点自己的随机秘密值与该节点到根节点路径上相邻节点的随机值的某种形式求出。例如节点〈1, 1, 1〉用r〈1, 1, 1〉,r〈1, 1, 2〉P , r〈1, 1, 3〉P可以算出k〈1, 2〉；利用k〈1, 2〉，r〈1, 2, 2〉P,r〈1,2,3〉P可以算出k1；再利用k1，k2P，k3P，k4P，k5P，eˆ(P,P)可以算出K。因为G2中的元素之一为eˆ(P,P)，当密钥需要多方协定时借助H在Z中映射它。假定共有节点n个，rk (k=1,…,n)是节点k的秘密值，令α=(P,P)，则协定后的群密钥

K形如：

2.2 基本密钥协定协议

若4大于协定密钥的节点数，则通过下面两个基本协议对密钥进行协定。

基本协议1 ：基于对定理2的运用，在A、B、C3个成员间将密钥协定：

A→B,C： aP，A选择秘密值a，广播aP ；

B→A,C： bP，B选择秘密值b，广播bP；

C→A,B： cP，C选择秘密值c，广播cP ；

最终A，B，C可计算出k = ê(P, P) abc

基本协议2 ：基于对推论2的运用，在A，B间将密钥协定：

A→B：ê(P, P)a，A选择秘密值a，广播ê(P, P)a ；B→A：ê (P, P)b，B选择秘密值b，广播ê(P, P)b ；最终A，B可计算出k = ê(P, P) ab

2.3 初始群密钥协定过程

设协定过程中存在暂时固定的网络拓扑结构，网络节点数为N ≥ 2，簇Ci共有m个，每个簇的网络节点数为ni，小组gj(1≤i≤m; 1≤j≤hi)共有hi=[(ni-1)/2]个，用#(gj)表示小组gj的节点数，#(g1)=3或2，#(ghi)=2或1，#(gu)=2（1〈u〈hi），小组代理由每个小组的最后一个节点代表，表示为S〈i, j〉，协调与其它组的通信事务。我们通过两个步骤对群密钥进行协定：

（1）簇密钥协定。

小组密钥的协定由每个簇的gi组完成，接下来以基本协议为依据S〈i,j-1〉和gi组的成员共同完成该小组密钥k〈i,j〉（1≤i≤m; 1〈j≤hi）的协定，k〈i,j－1〉是此时S〈i,j-1〉选择的随机秘密值，也就是j-1及以下层密钥的协定值。最后k〈i,hi〉即为簇密钥ki。能够在全部簇中并行执行簇密钥的协定，以使簇密钥的生成时间得以减少。

以簇密钥生成过程为依据，密钥树的一层就是每个小组，叶子节点就是组成员，连接借助虚拟节点实现，能够最终完成逻辑簇密钥树的构造。针对簇密钥树，到树根路径上相邻节点的随机值r的某种形式（节点数为3，就是rP，否则为(P,P)r）每个节点都知道，簇密钥可以被每个叶子节点计算出来。在一个簇中，簇的代理并不一定是簇头，簇头负责响应网络节点的加入和移除，通知簇的代理发生了网络拓扑结构的变化，由代理引发密钥更新过程。

（2）群密钥协定。

生成群密钥由簇代理代表该簇参与，网络节点就是每个簇，一个簇就是整个网络，以协定簇密钥类似方法为依据协定群密钥，进而完成群密钥树的构造，到树根结点路径上相邻节点的随机值r的某种形式的值（为rP或eˆ(P,P)r）每个节点都知道，群密钥K能够被每个叶子节点计算出来。

2.4 群密钥更新过程

节点具有较强的移动性和不稳定的网络拓扑结构是ad hoc网络的特点，要保证簇密钥的安全，必须对节点的变化进行跟踪并适时地对簇密钥进行更新。簇头节点负责对网络分簇变化的响应，向簇代理进行通知并对簇密钥进行更新，最终对群密钥进行更新，群密钥更新由下面7种事件引发。

（1）单节点加入（Join）

若在网络中加入节点V，以层次路由协议为依据，在簇Ci中加入该节点，V加入事件的响应由簇头作出，同时向该簇的代理通知，与V共同更新簇密钥，设用hi个小组对簇Ci进行划分，为使下标得以简化， 让hi=n ，则情况如下：

（a）若2=#(gn)，在加入V后将其划分到第n组，簇密钥树的高度不增加，以基本协议1为依据，在〈i, n, 1〉、〈i, n, 2〉和V间对簇密钥ki进行更新，以下是其过程：

〈i, n, 1〉给〈i, n, 2〉及V单播 ：k〈i,n-1〉P ；

〈i, n, 2〉广播 ：r〈i,n,2〉’P，即S〈i,n〉换一个秘密随机值r〈i,n,2〉’，给〈i, *, *〉广播r〈i,n,2〉’P ；

V广播 ：rvP，给〈i, *, *〉广播rvP。

（b）若3=#(gn)那么在加入V后将划分到第n＋1组，1是簇密钥树高度的增加值。以基本协议2为依据更新密钥，以下为其过程：

进而以（7）为依据，群密钥更新过程由簇Ci发起。

（2）单节点移除（Remove）

设〈i, l, v〉为移除的成员，V移除事件的响应由Ci的簇头作出，同时向S〈i,l〉通知更新簇密钥，设用hi个小组对簇Ci进行划分，让 hi=n ，情况如下：

（a）如果1〈 l ≤ n，且#(gl)=3，则〈i, l, 2〉成为新的层代理S。一个新的随机秘密值r'由S选择，求得

〈i,l〉〈i,l,2〉〈i,l〉，接着将新的求出，广播新的也能被其它成员计算出来。 若 #(g1)=2，那么的更新将由S〈i,l-1〉完成，将新的求出，接着将（t=1,...,n-1）广播给其他成员。此时密钥树降低一层，即n=n-1。此时只需1次广播消息。

（c）若将簇头节点移除，就要重新划分该簇，其实现由层次路由协议来完成，当簇被路由协议重新建好之后，进而以上述方式为依据来完成簇密钥的更新。此外，设ad hoc网络的群是动态对等的，具有相当的节点处理能力，因为能够单跳到达一个簇中的节点，所以簇头可以被简单地指定为该簇中任一其它节点，以（a）或（b）的办法为依据完成簇密钥的更新[6]。

（3）多成员同时加入（Merge）

针对实际的应用，或许会有许多成员同时加入，其可能性有二：

（a）若是离散的成员，以(1)的做法为依据逐个加入。

（b）若一个簇由这些成员组成，那么以情况（5）为依据完成群密钥的更新。

（4）多成员同时移除（Partition）

因为受到网络故障的影响，或许会有许多成员同时离开。设〈i, l, v〉为其中对应簇密钥树层数最低的节点。若l 〉1，由l-1层的S〈i,l-1〉执行Delete操作；若l=1，由S〈i,2〉执行Delete操作。再按（7）更新群密钥。

（5）簇的加入（Cluster Merge）

设在当前群中加入簇Ci，该簇要以IKA的办法为依据将簇密钥ki预先生成，接着与原群的代理共同以IKA中生成簇密钥的方法为依据完成群密钥的更新，同时将必要的消息广播出去，以使新的群密钥能被全部节点计算出来。此时群密钥树的最高层就是簇Ci，同时新的群代理也是簇Ci。

（6）簇的移除（Cluster Partition）

用一个网络节点对应每个簇，一个簇对应整个网络，该簇的移除采用类似于单节点移除的方法完成，同时将必要的消息广播出去，以使新的群密钥能被全部节点计算出来。

（7）密钥更新（Key Agreement）

群密钥的更新在上述（1）～（6）情况下都需要进行。都是通过某个簇Ci的代理触发更新群密钥。基于密钥树的角度，在更新过程中比Ci更低层的簇并不参与，只要将或广播出去，新的群密钥能被全部节点计算出来。

3 协议性能分析

3.1 通信量分析

（1）路由协议的通信量

不管底层的路由协议是否被密钥协定方案考虑到，总会存在路由协议的通信开销，如果可以借助对路由协议某些结果的利用服务密钥协定方案，或许就会使密钥协定协议的通信量得以降低。

基于4种动态情况，对比分析3种密钥协定方案的通信量。如表1所示：

表1 CEKAP，TGDH和RSTR方案的通信量对比

画图表表示如图2、图3所示：

图2 CEKAP，TGDH和RSTR方案的通信量对比

图3 CEKAP，TGDH和RSTR方案的通信量对比

以事件响应层的节点数为3或2为依据，CEKAP协议取不同的消息数、单播和多播数，详见表1所示。CEKAP方案有常量的轮数与消息数，基本相同于RSTR协议，并改进了“簇合并”方面的性能。同时，和TGDH协议相比，大大提升了“划分”方面性能。但是，在分析TGDH和RSTR时，都没有将单播的问题考虑进去，若设平均每次单播经过的转发至少有1次，那么显然性能更好的是CEKAP协议。所以降低路由协议与密钥协定协议的通信量时，本方案有着更低的通信量。

3.2 计算量分析

标量乘（Scalar）、求对（Pairings）与模幂运算（Exponentiations）是基于BDH问题的密码协议的计算量。对比操作AKA时CEKAP、TGDH与RSTR方案计算量，详如表2所示：

表2 CEKAP和TGDH，RSTR方案的计算量对比

画图表表示如图4所示：

图4 CEKAP和TGDH，RSTR方案的计算量对比

在表2中分析的是CEKAP的平均情况下的数据，从表2中可知，h、m、h2是影响CEKAP方案计算量的主要因素，也就是受群密钥树的高度、簇的数目、最大簇密钥树的高度及状态改变的网络节点的位置等的影响。操作“加入”与“簇划分”计算量如图5所示：

图5 CEKAP和TGDH，RSTR方案的计算量对比

总的来说，正相关于m，越少的分簇，就会有越低的计算量。当次高层的结点数取值不同时，操作“簇合并”的计算量也不一样，若取值为2，标量乘运算3次就可以；若取值为3，求对运算与模幂运算各2次，要优于TGDH与RSTR。

在表2中操作“移除”的计算量是最大的，其受h1，h2与移除节点的位置的影响，移除结点和树根靠的越近，就会有越小的计算量。因为h1反比于h2，所以“移除”的计算量也会受到分簇方式的影响，使“加入”与“簇划分”计算量得以降低的同时或许也会使它的计算量增大。

4 总结

文章以双线性映射与ad hoc网络中的层次路由协议为基础，将一个密钥协定协议CEKAP提出，独立性较之以往密钥更好，使前向与后向的安全得以同时保证。保证密码是协议在安全性方面主要考虑的。与改进型STR方案的通信量基本相同，要优于TGDH，同时，因为是网络都是单跳这一假定条件得以削弱，将会更好地应用到实际中去。Merge操作的计算量明显优于TGDH与改进型STR方案，不过因为要对双线性映射进行计算，基于双线性对的密码协议普遍存在的一个问题，也是CEKAP协议将会面临的，从而处理某些操作时高于只需模幂运算的协议的计算量。在发现快速求对算法后，将会逐步改善这一问题。

[1]詹思瑜,李建平. 基于遗传算法的Ad hoc路由协议优化[J]. 小型微型计算机系统,2012,01:24-27.

[2]刘静,王赜. 可信链在Ad Hoc网络的传递[J]. 计算机工程与应用, 2012,04:91-93+192.

[3]邵志毅,吴振强,马亚蕾,王改宁. 一种Ad Hoc下的网络编码模型NCMA[J]. 计算机工程与应用,2012,04: 100-103,110.

[4]孙梅,赵兵. 基于身份的Ad Hoc网密钥管理方案[J]. 计算机应用, 2012, 01:104-106+122.

[5]夏文洁,李千目,刘凤玉,孙晋厚. 基于拟生灭过程的多跳Ad hoc网络洪泛方式下拥塞控制及饱和条件研究[J].计算机科学, 2012,04:110-113.

[6]Mittra S.Iolus:A framework for scalable secure multicasting. In:ACM SIGCOM Computer Communication Review[J]. New York: ACM Press, 1997. 277-288.

Based on the Research of the Ad Hoc Network Protocol Agreement

Yang Cheng, Zhan Yongzhao
(Changzhou College of Information Technology, Changzhou 213164,China)

Routing technology is a key technology of the Ad Hoc network, and it is also one of the most important factors that affect the performance of the network as a whole. As the routing protocols in the traditional fixed networks no longer adapt to the dynamic changes in the topology of Ad Hoc Networks, new Ad Hoc routing protocols must be redesigned. Starting from the basic concept of the Ad Hoc network, an ad hoc network communication effective key agreement protocol based on bilinear pairings and hierarchical routing protocols is proposed. It supports the establishment and dynamic update of initial group secret key and has less traffic that corresponds to the logical key agreement model and actual network topology. The experiment and performance analysis show that the proposed protocol is very effective in the situation of large range, strong ability of equipment processing and poor network communication environment.

Ad hoc Networks; Key Agreement; Hierarchical Routing; Bilinear Pairings

TP311

A

2014.12.17）

1007-757X(2015)03-0008-04

国家自然科学基金项目（61202474）

杨 诚（1975-），男，常州信息技术学院，副教授，硕士，研究方向：计算机网络技术、移动通信技术，常州，212013

詹永照（1962-），男，常州信息技术学院，教授，博士生导师，研究方向：人机交互、分布式计算，常州，212013