基于MIS的临床决策支持系统（CDS）优化方案

此类算法的基本思路是先进行计算，然后连接一个MIS。计算一个MIS有两种基本策略。一种策略是基于单个前导序列，另一种策略是基于多个前导序列。下面，我们介绍针对这些策略的两种代表性算法。

参考文献（Alzoubi et al.，2002）提出了基于单个前导序列的CDS构建算法的两个版本。在两种算法中，分布式前导序列选择算法（Cidon and Mokryn，1998）用来构建根生成树。基本思路是将网络中的所有节点划分为若干个组。每个组包含一个候选节点及其支持节点域。这些组反复进行合并，直到仅存在一个最终成为树根（前导序列）的候选节点。然后，根据节点的秩，采用一种迭代标记策略来将树中节点划分为黑色（支配者）或者灰色（被支配者）。节点的秩是一个数对{hop_count，ID}，其中hop_count表示距离生成树根的跳数。标记过程从树根处开始，在树叶处结束。在初始化阶段，具有最低秩的节点将自己涂成黑色，并广播一条“支配者”消息。如果某个节点接收到任何“支配者”消息，则它将其本身涂成灰色，并广播一条“被支配者”消息。如果某个节点接收到来自于所有低秩邻居的“被支配者”消息，则它将自己涂成黑色，并发送一条“支配者”消息。当到达树叶节点后，算法中止。所有黑色节点形成一个MIS。

为了连接MIS中的节点以形成一个CDS，首先根节点加入CDS并广播一条“邀请”消息。然后将“邀请”消息中继到与当前CDS相距两跳的所有邻居节点。黑色节点首次接收到“邀请”消息后，它将CDS与中继该消息的灰色节点连接起来（于是灰色节点加入CDS）。然后，黑色节点广播一条“邀请”消息。当所有黑色节点全部加入CDS时，该过程中止。由此形成的CDS的性能比最多为8。

算法工作原理如图2-5所示。假定采用前导序列选择算法（Cidon and Mokryn，1998）来计算树根在节点0的生成树。实线代表生成树的边，而虚线代表UDG的各边（生成树的每个边也都属于UDG）。根据该算法，节点0被涂成黑色，并向其邻居节点2、4和12发送一条“支配者”消息（见图2-5a）。当收到消息后，节点2、4和12被涂成灰色，并发送“被支配者”消息。例如，节点4向其邻居节点0、5、7和10发送“被支配者”消息。由于节点5收到了所有低秩邻居（仅有节点4）发送来的“被支配者”消息，因而节点5被涂成黑色。图2-5b给出了标记过程结束后各节点的颜色。最后一步是从树根开始构建支配树。节点0向其邻居节点广播一条“邀请”消息，这些邻居节点将消息中继给与节点0相距两跳的黑色邻居3、5和7。这些黑色节点与其中继消息的灰色邻居2、4一起加入支配树。最后，支配树中的所有黑色节点形成一个CDS（见图2-5c）。

(www.xing528.com)

图2-5 基于MIS的算法

参考文献（Cheng et al.，2004）提出了一种基于多个前导序列的CDS构建算法。该算法的基本思路如下：首先，在单跳邻居中具有最小标识符的每个节点，将其本身标识为一个前导序列。这些前导序列充当形成森林的树根。然后，通过计算一个或两个节点的链，来连接相邻树。在算法应用期间交换的消息数，与网络节点数成线性关系，且性能比最多为147。

本节介绍的基于MIS的CDS算法存在的缺点是：需要使用大量消息来构建和维护树结构。在现实应用场景中，这些消息除了容易造成消息开销和能耗外，还可能会导致媒体接入层和实际物理层的决策错误。