分布式嵌入系统中的交互一致性

   许多应用与人身安全或设备安全有密切联系，随着安全性要求的提高，希望设备或系统在其构成的部件与控制装置发生故障时仍能保证安全，即故障-安全（failsafe）的特性。系统是由子系统组成的，子系统有故障时有控制地停止工作（failsilent，故障-静默模式），对系统而言仍是故障，因为它不再提供原定的服务了，这有可能引起全系统功能的失效。所以，安全是要从最高层的全局来分析的。例如对一辆汽车，刹车系统整体不能用故障-静默来达到安全，而应该是故障后仍能工作（failoperatiONal，故障-仍工作模式），或至少是性能下降一点仍能工作（faildegraded，故障-降格工作模式）。

　　单一部件的架构（包括硬件与软件）有故障而失效时就无法继续提供服务了，它不能满足故障-仍工作模式或故障-降格工作模式的要求。这就必须采用有备份的冗余架构，每一个备份都能完成出故障的原来部件的大部分或全部服务工作，维持系统正常运行。备份工作的交替就要求它们对工作状态（系统的输入、应该的输出和谁不该输出）有相同的看法。这种相同的看法要通过信息交换并通过协议才能建立，并称为交互一致性（interactive consiSTency）。

　　有一部分控制对象存在功能上互为冗余的可能性，例如汽车的4个轮子的刹车，当一个轮子的子刹车系统（设备或控制装置）有故障时，修正其他轮子的刹车力便可以实现总体刹车系统的故障-仍工作模式或故障-降格工作模式。此时对单个轮子而言，它只要能实现故障-静默即可。显然，单个轮子的可信赖性要求被降低，会造成成本的大大降低。在这种情况下，轮子的控制器之间就存在交互一致性问题。

　　来自汽车电子大佬Infineon和Delphi的研究报告[1]比较了基于这种互为冗余的分布式冗余刹车系统与集中式仅控制器冗余的硬件成本，指出成本可大为下降，并称集中式有控制器冗余的刹车系统将会废止，这对我国汽车电子业者有警示意义。不过，该文并未提到用硬件集中方案也可实现对象互为冗余的刹车系统（这二种方案成本差别将不会太大）。此时由于通信有较大不同，交互一致性问题会不一样，加上其他因素，它们的优劣有待研究。但至少分布式互为冗余刹车系统是一个备选方案。参考文献[1]非常概述地提及了控制方案，并未谈及技术细节以及采用的协议。本文将根据交互一致性的理论，对实施这类应用中可能遇到的问题进行分析。

　　1  SM算法

　　对交互一致性的研究已经有30年了，它被称为拜占庭将军问题算法（Byzentine Generals Problem）。原始文献有2个版本[23]，1980年的文章引用很多，但是公认很难读懂[4]。原来的讨论是针对点对点通信进行的，本文根据对参考文献[3]的理解，针对总线方式通信加以展开，这会引入作者的看法。参考文献[3]提出：一个冗余系统的“所有无错节点应该采用同样的输入（这样才能产生同样的输出）；如果输入系统没错，就应该采用输入的值（这样才能产生正确的输出）”。参考文献[3]提供了二种解决算法：一是口传消息算法OM（Oral Message Algorithm），二是签名消息算法SM（Signed Message Algorithm）。对容许m个错而言，OM算法需要3m+1个节点以及m+1轮消息传送，SM需要m+2个节点和m+1轮消息传送。这是2种原理与性能有很大差别的算法。OM算法依靠消息转述与表决来确定从节点的输入，当无法进行表决时要采取预定义的缺省输入。当主节点有拜占庭错且错值占多数时，无错的从节点间看法虽是一致的，但是是不正确的。SM算法依靠逐级检验与重复转发，可以发现各节点（包括主节点）的错，而且只要有一次正确收到就可以了。由于性能好且需要的从节点数较少，SM值得进一步探究。下面以总线通信时的情况来介绍SM的做法。

　　① 对需要交换数据并保证一致的n=m+2个节点而言，可将问题作分解，每个节点可轮流作为主节点对其他节点传送消息，实施SM算法。

　　② 每个通信帧含有两部分内容：数据d和与d有关的签名a。根据参考文献[3]，签名要不被有错节点作伪，应该各节点各不相同且每次都不同。笔者认为根据工业应用可以不这样要求，详见后文。

　　③ 通信各轮的帧内容如下：

　　第1轮，主节点发自己的数据与签名(d:a0);

　　第2轮，各从节点转发由第1轮收到的帧再加自己的签名((d:a0):aj)，其中 (j=1，…，n-1);

　　以后各轮，各从节点转发由上一轮收到的帧再加自己的签名((…((d:a0):aj)…):ar)，其中 (j,…,r∈{1,…,n-1}; j≠…≠r)，也就是说已经经过本从节点转发的内容不再转发。

　　由于是通过总线广播而不是点到点通信，通信量只要计算不同的帧的个数就可以:N=1+(n-1)+(n-1)2+…。总的通信轮数为m+1。

　　④ 每个从节点保存一个供选择的集choice，初始化时为空：choice{Φ}。choice的更新可在m+1轮通信结束之后进行。更新时先检验签名的有效性，只有全为有效的才可把该帧的d添加到choice中，如果choice中已有，就不重复添加。点对点通信按参考文献[3]的做法，出现主节点错时choice会有多个元素，总线通信时主节点的签名计算只有一次，按本文做法（见下文）choice只会有一个元素（真值或空）。

　　⑤ 参考文献[3]证明了在下列假设得到保证的条件下所有无故障从节点会得到相同的choice：

　　A1发送的消息总能正确送达；

　　A2每个节点知道谁在发送；

　　A3消息的缺失可以检测出来；

　　A4签名不能被作伪，作伪时可检测出来；

　　任何从节点能检测出签名是否有错。

　　SM算法的有效性与此有关，通信时发生错帧漏检的情况相当于发生一次错，要在容错的次数设计上加以考虑。[!--empirenews.page--]

　　参考文献[3]建议了一个签名的方法例子，即用密钥ki对数据d求出签名a: a=(ki·d)mod p，其中p是2的幂，ki是小于p的一个奇数，接收节点用另一个密钥ki-1验证：d=(ki-1·a)mod p。ki和ki-1有如下关系：(ki·ki-1)mod p=1。这样，有错节点能作伪的概率为1/p。这种方案作伪者要不知道加密的办法才行。参考文献[3]认为要求更严的场合要采用密码学的方法。

　　从工业应用来看，有错节点的作伪的可能性来源乃是电磁干扰，对人为的黑客攻击应另外采用对抗措施，所以可以采用较为简单常用的CRC校验和作为签名。注意，这个CRC校验和是应用数据的校验和，不要混同于通信帧的校验和。在冗余系统里关心的是应用数据的一致性，而应用数据在MCU与通信控制器的传递过程中可能出错，通信帧的CRC校验不能覆盖这一错。例如，应用通过FlexRay的二个通道传送同一数据时，由于写入输出缓冲器的过程是分时的，如果其中一次受到干扰，应用数据与应用CRC（签名）不再匹配，那么接收方将能发现应用数据的传送错而加以丢弃。

　　在总线广播通信中，由于各节点受干扰请况的不同，它们可能接收到不同的帧，一旦又发生了错帧漏检，那么就会发生一个节点给其他节点送不同值的情况，这与点到点通信的情况一样，是一种拜占庭错。同时，转发过程又涉及MCU与通信控制器的传递过程，其中也会发生错，所以转发过程也用数据加签名的方式。例如节点p在第3轮收到帧(((d:a0):aj):ai)时，检验ai的签名是否正确，如果错，那么在节点j到i的转发通信中有错。如无错，继续对((d:a0):aj)作aj签名的检验，如果错，那么在节点0到j的转发通信中有错。如无错，再对(d:a0)作a0签名的检验，如果错，那么在节点0的MCU与节点0的通信控制器通信中发生了错，或者它在计算签名时发生了错。

　　未通过签名检验的数据将不提交到choice，如果主节点无错，从节点有m+1个，那么在第一轮中至少有一个从节点正确收到，在以后各轮中其他有错节点的转发将不会影响这个节点的choice。现在可以发现SM算法的一个有趣的特性：如果某些从节点只是发生了瞬时故障，由于无错节点的转发，它仍然有机会得到相同的choice。

　　由于采用总线广播，主节点可以收到被转发的自己的帧，因此可以进行自检。若全部转发结束后自检不通过，就可以采取进一步的措施，例如本节点重算签名并写通信控制器，或者立即进入故障-静默模式。

　　SM算法假设帧的丢失可以检测出来，这要靠另加的超时报警单元。一旦时间窗口关闭，各节点就根据已收到的各帧进行choice的更新工作。

　　一次SM算法结束后就可认为将开始新的一次SM算法，也就可以初始化choice。如果将每一个节点开始发本节点数据的次序固定下来，并将以前节点开始发转发的时刻来预置本地定时器，那么在预定的时间窗口内上一节点因故障而未转发的错误可以被发现。上一节点转发结束的信号或时限到可用来触发本节点开始转发。

　　2  互为冗余

　　经过执行SM算法，所有无错节点和有瞬时故障的节点都可得到其他节点发送的一致的输入值。有错节点发出的输入值被所有节点（包括有错节点本身）识别，不被用来进一步作计算，此时有错节点进入故障-静默模式，其余正确节点直接开始重新分配刹车力矩的算法。输入值交换无错时每一个节点用相近的控制算法计算每个轮子的控制输出（刹车力矩）。然后再用SM算法交换各自计算结果，每个节点将有一致的各节点的输出值。

　　在每个节点计算时，会因干扰（如EMI或热冲击等）而出现错误输出值。或因其他附加条件（例如刹车力矩传感器的失效，MCU自检错）等因素，人为使该节点计算得的输出值为非正常值。由于SM算法，这个错误的输出值一致地传送到每个节点。

　　这样各轮子的刹车力矩就有4个来自各节点的冗余计算结果，这是一个二维的矩阵。在矩阵中找出有错的刹车力矩是哪一个，以及有可能发生永久故障的节点是谁。由于计算结果是模拟量，冗余系统又为了避免共同错（common mode faults）强调各备份间的多样性。同样算法也可能会使结果有微小差别，所以与其他计算结果偏离大于预定限值时视为有错。

　　有严重故障的节点的输出值可能全是错的，有瞬时故障的节点可能只有一个计算结果是错的。由于所有正确的节点均采用同样的判别原则，一致的输入数据，它们作出同样的判别结论。

　　如果有一个节点的一个刹车力矩计算是错的，那么可认为这个节点遇到了瞬时干扰。此时仍可按多数或平均方法确定各轮子的刹车力矩，各节点按该轮子对应的刹车力矩加以执行。

　　如果有一个节点的刹车力矩计算都是错的，那么确定这个节点发生了一个严重的也许是永久性的故障，此时所有正确的节点将按补偿算法重新计算刹车力矩输出，以使车子减少偏航，减少颠簸。

　　严重的错误是发生通信链路断开，正确节点按SM算法用超时可以发现有错节点。断开链路的节点按SM算法发现所有其他节点都错了，这时它应该判为自己错了，对本轮子的刹车力矩应取一个缺省值，这个缺省值也是在其他正确节点补偿算法中采用的对该轮子的缺省值。

　　由上可见，由于出故障后节点只须保证故障-静默模式，刹车力矩的再分配保证了整车的故障-安全特性。控制器硬件将大为简化，虽然初期软件成本增加，其后可以分摊，总体成本是下降的。[!--empirenews.page--]

　　3  CAN在这类应用中的可能性

　　3.1  带宽

　　对4个轮子节点和1个指令节点（由踏板或其他系统转发刹车命令，转发由轮子来的轮速信号）构成的互为冗余系统，要容许1个错时，采用SM算法需要2轮通信，对5个节点需要交换输入数据1次，共25种帧，4个节点交换输出数据1次，共16种帧。如果要求每5 ms进行一次协调，传送41帧，对CAN而言将非常吃紧，这就是经常提到的CAN的带宽局限。这里假设了冗余后的系统只容许5 ms内有1个错。如果从互为冗余刹车系统的性价比考虑，为了此带宽问题，设立专用的CAN总线也是值得的。

　　SM算法实际上对数据的传送有很大的重复，在本例中对一个从节点而言它收到了5次。如果从节点只是瞬时有故障，它一定会收到正确值。按照SM算法，为了对付m个错，需要m+1个从节点，因此虽然互为冗余系统有5个节点，并不需要每个从节点都进行转发。例如取3个从节点转发输入，那么每5 ms就传送36帧，可以缓解带宽瓶颈。如取2个从节点转发，带宽变为每5 ms传送27帧。

　　3.2  确定性

　　有一种观点认为只有时间触发的通信协议才能满足高可信赖性要求。但这是片面的。在本例中，如果把所有互为冗余系统需要传送的消息都设为较高优先级，那么在总线上它们将像一个长帧不受阻挡延迟，只要带宽容许，就能送达。至于这些消息内部的到达先后，在SM算法中并无影响。更广义地讲，只要把CAN的触发事件与时间一一对应，它也可实现时间触发的功能。利用CAN的竟争发送，有错未发节点的带宽可被其他节点尽早利用，SM算法所需的时限计时器只要一个就够了。

　　3.3  错帧漏检

　　由于CAN中位填充规则对CRC的影响，根据笔者的研究，它的错帧漏检率较大，远大于Bosch CAN2.0规范的数据。但是由于SM算法中签名的存在，这一问题已免除或缓解。当签名也用本文建议的CRC方法，那么签名错而漏检的情况可以用CAN错帧漏检率同样的方法分析与改进。

　　3.4  容错

　　SM算法假设发送的消息总能正确送达，通信中可检出错要排除在外。这就需要某种纠错或冗余。CAN的出错自动重发是很好的纠错措施，但它只能应对瞬时干扰，对物理通道上的故障如断线、短路等，需要用容错CAN协议ISO118983的收发器。此种收发器的带宽更小，标准为125 kbps，较好的MAX3054可达250 kbps。如果互为冗余刹车系统的控制周期定为20 ms（即容许20 ms内有一个错）（参考文献[5]中引述的线控转向的容许失控时间为50 ms），那么CAN在满足容许物理故障时还能满足SM算法的带宽要求的。从概率上讲，由于重发而占用的带宽增量并不大。

　　4  小结

　　分布式互为冗余系统的特点是用重新分配的原理实现故障-安全。并不是所有系统都能采用这种方法。但是在分布式系统中保证数据的一致性是很重要的，例如同一数据可能应用于不同目的的控制系统中，这些系统在分开设计时就默认了数据一定是一致的。如果发生了不一致，这些系统的交互影响就难以预测。因此SM算法有其现实意义。

　　SM算法可以发现节点MCU与通信控制器的传递过程中的错，以及通信中的拜占庭错，这是一个非常重要的特性。由于本文发现了SM算法的签名转述同时具备的二个功能─重复发送和接收认可，使主节点也能与其他节点达到一致，这大大提高了容错实现的简易性。一般地说，拜占庭错难以发现，当双互备份架构输入有拜占庭错时，无法确定谁错而无法实现故障-静默，甚至可能出现互相冲突的输出。采用SM算法，可实现双互备份架构输入的一致性，再借用其他系统的节点的部分计算能力，可用使双互备份架构实现等效的三重备份输出的一致性。这在经济上有巨大意义。

　　本文根据总线通信分析了SM算法的实施方法以及CAN在用于SM算法时的一些问题。CAN是成熟的技术，成本较低，尽量扩展其应用是理所当然的事。就互为冗余刹车系统而言，CAN仍然是可以应用的。参考文献[3]提到了一种在2002年还是研制中的时间触发协议，现在看来，可能是FlexRay协议。毫无疑问，FlexRay的带宽优势很大，但是对其的研究还有待深入，例如它的时钟同步依赖于传送电缆上的模拟电平跳变，毛刺可能改变跳变位置，从而破坏整个协议的基础时钟。

　　SM算法需要的消息签名转发，均需要MCU的参与，对FlexRay或CAN而言，要高层协议或软件中间件实现，耗费时间，增加中间环节，增加了时间抖动与受干扰可能性，总之效率不高，并不理想，最好是用专门的硬件实现，这是值得探讨的事。