基于随机数发生器的设备地址自动分配方法

张 垒，杨启帆

（1.江苏大学 电气信息工程学院，镇江 212013；2.上汽大众汽车有限公司 质保部，上海 201800）

基于随机数发生器的设备地址自动分配方法

张 垒1，杨启帆2

（1.江苏大学 电气信息工程学院，镇江 212013；2.上汽大众汽车有限公司 质保部，上海 201800）

总线通讯常用于工业控制系统，系统常为一个主机、多个从机的结构。该文传统的总线通讯网络多采用拨码等手工方法设置设备地址，系统的自动组网及地址的自动分配一直是个难题。提出了一种新的基于随机数发生器的自动组网与设备地址分配方法，实现了设备的自动组网与地址的自动分配。该方法适用于无主机的控制系统，可自动选出主机，上电即可自动组网与分配地址，且所需时间更短，分配效率更高。实践证明，该方法稳定可靠，具有良好的应用和推广价值。

总线通讯；自动组网；地址分配；随机数

随着计算机、网络技术的发展，自动控制技术广泛地应用于工业、交通、服务等领域，控制的形式也由点对点通信逐步扩展到点对多的通信模式。串行通信作为一种简单、廉价的通信方式在工业控制中广泛应用，由于实现成本低、传输距离远、抗干扰能力强的特点，使总线型多CPU网络控制系统得到了推广与发展。

在以往的总线通信系统设计中，通常使用拨码开关或者人工输入方式逐一对从机地址进行设置。在目前的一些自动组网的算法中，通常需要指定主机，且主机故障后无法继续组网。另外，现有的一些随机时隙算法采用机号生成随机数，生成的随机数重复率高且无法改变，地址无法一次分配成功。在此，提出一种新的基于随机数发生器的自动组网与设备地址分配方法，将从机ID与系统时间t通过CRC计算生成随机种子，可充分利用每个二进制位的信息，生成唯一最小随机数的概率趋向于1，极大地提高了地址分配效率。该方法适用于无主机的工控系统，并且在系统运行过程中如果主机出现故障也能重新组网，原理是在无主机的系统中随机选出1台设备成为主机，通过随机生成从机答复时间，尽量使从机的回复信号不冲突[1]，从而使得从机的信息能够快速识别，以实现其地址的快速分配。这一算法的优势在于上电即可自动组网与分配地址，速度快且稳定，所有过程均自动完成。

1 总线通讯网络的结构特点

以RS-485通讯网络为例，鉴于需要实现多节点通讯，RS-485通讯网络使用共享总线的半双工传送方式，即在同一时刻主机和从机只能有1个发送数据而其他的只能接收数据。网络结构上，采用主从结构方式实现通讯，主机和从机通过RS-485总线连接在一起。本算法适用的无主机工控系统，上电后所有从机生成1个随机数和延迟时间，延迟时间最短的从机自动成为主机。系统拓扑结构简图如图1所示。

图1 系统拓扑结构Fig.1 System topology diagram

主机的作用是发送命令与分配地址；从机实现具体的业务需求，不主动发送命令或数据。系统中所有的单元都可以收到通信链路上的数据包，各从机根据通信数据包的目的地址进行识别：如果数据包中的目的地址与本单元的设备地址相同，则处理该数据包；否则丢弃该数据包。

2 自动组网与设备地址分配方法

2.1 基于随机数发生器的算法设计思想

在自动组网时，将面临系统有无、主机两种情况。系统上电后，主机将立即发送地址分配命令，所有从机设定等待时间为1 s，并生成1个随机数x，由x生成延迟时间T2。若在1 s内从机收到主机的地址分配命令，则进入地址自动分配环节；若1 s内从机未内收到主机的命令包，表示系统无主机，则在1 s等待时间到后进入延迟环节，第1个到达T2的从机成为主机，并将本机地址设为00，广播地址分配命令进入地址自动分配环节，其他从机取消成为主机的进程。

在地址分配时，各从机设定1个基于本机时间和生产序列号ID的随机数xi，由xi生成延迟回复时间2，主机收到第1个回复后，其他从机不再回复，主机开始分配第1个地址。第1个地址设置完成后，未分配地址的从机生成1个新的随机数，主机分配第2个地址，如此往复，直至各从机地址全部分配完毕。

如果在地址分配的过程中，主机发生故障无法通讯或自动组网，此时需要在从机中重新选出主机并重新进行地址分配。方法是在主机发送地址分配命令后由从机设置1个适当的延迟时间2 s，若2 s后从机未收到主机发送的数据包，则生成延迟时间T2，第1个到达T2的从机成为主机。

地址分配完毕后，系统将正常工作。每隔2 s，如果主机没有发送正常的命令，则广播1条“心跳”命令，该命令不含任何内容，从机在5 s时间内未收到主机发送的正常或“心跳”命令表示主机故障，此时将开始重新组网，方法同上。

2.2 随机数的产生

随机数x是延迟回复时间2的重要组成部分，因此生成适当的随机数对于各从机的随机延时应答至关重要。计算机不会产生绝对随机的随机数，而只能产生伪随机数。所谓伪随机数通常由数学公式产生，如果生成随机数的算法确定了，那么这个随机数序列也就确定了。从数学意义上讲，伪随机数某种对应映射的产物是完全不随机的，只要知道随机数的种子以及相应的参数，就可以预测下一状态的随机数。但是，只要伪随机数通过一系列测试检验，而且其有足够长的周期，那么在一定范围内，还是可以把它当作真随机数来使用[3]。对伪随机数而言，其实现算法显得尤为重要。因此，为了使各从机生成的随机数尽量分散，本算法选用从机ID和系统时间t通过CRC码编排为随机种子，再通过线性同余法生成随机数。

随机种子x0由从机ID和系统时间t采用CRC公式生成，长度为2 B。其中，t为读取的系统时间，s，长度为 1 B；ID 为 6 B，由高到低分别为年（2 B）、月、日、机号（2 B）。加入系统时间t的目的在于使每次的随机种子都不同，降低了产生相同随机数的概率，即使产生了重复的随机数，由于下次生成随机数时的时间已变，随机数也将改变。

本算法借用线性同余法的思想生成随机数，其公式为

式中：x为随机数；x0为随机种子；a为乘子；b为增量；M为模；变量a，b，M均为常量。通过选取适当的a，b，M可使x充分随机，产生的随机数具有均匀性好、独立性好等特点[4]。 在此，取 a=31，b=23，M=101，其中模M可随着从机数Y的减少而适当减小。M过大会造成随机数x和延迟回复时间T2变大，M过小则会导致随机数的重复率过高。模M一般取约为初始从机数Y的3倍的质数。最终的随机数生成公式为

2.3 通信协议说明

本协议采用异步串行，半双工传输方式。在同一时刻主机和从机只能有1个发送数据而其他的只能接收数据。数据在串行异步通信过程中，是以报文的形式一帧一帧发送[5]。拓扑结构为单主多从，从机地址的设定范围为1～247，0为主机地址。主机对所有从机广播发布信息，每个从机都要反馈响应给主机。

本协议包括接收地址ADR，命令码CMD，数据内容DATA，校验码CRC。由于主机采用广播方式，故接收地址ADR只有2种，00（主机）和FF（广播轮询）。命令码CMD为1 B，首位为0：下行报文；8：上行报文。ID共6 B，从高到低依次为年（2 B）、月、日、机号（2 B）。例举一典型的地址自动分配协议，如表1所示。

表1 地址分配协议Tab.1 Address allocation protocol

2.4 算法步骤

步骤1所有设备生成相应的随机数xi（i=1，2，…，Y；xi∈［1，Y］），延迟时间 T2=xik，其中系数为主机发送最长数据包到从机接收所需时间。系统规定所有设备同时延时，并在延迟时间到后广播一条地址分配命令。如果在延时期间内，设备收到了其他设备发来的地址分配命令，本机取消延时进程。因此，生成最小随机数的设备将成为主机，并将本机地址设为0。

步骤2主机广播地址分配命令，并设定接收数据等待定时时间T1=（Y+1）k。从机收到地址分配命令后开始定时2 s，并判断本机是否已经分配地址。若已分配地址，则不应答；若没有分配，则生成相应的随机数xi和延迟时间T2，达到延迟时间后从机向主机发送含有本机ID的应答包。

步骤3主机检测T1时间内有无应答包。若有应答且校验码正确，主机广播含有从机ID和地址ADR的数据包；如果校验码出错，表示生成了2个相同的最小随机数，则转至步骤2。若无应答，判断是否N=20，若不等则转至步骤2；若相等，表示连续20次无应答，地址分配完毕，算法结束退出。

从机检测2 s内有无主机发送的数据包，若无数据包，表示主机故障，转至步骤1；若收到数据包，则检测数据包中ID与本机ID是否匹配。若ID不匹配，则丢弃数据包；若匹配成功，则保存地址ADR并设置，向主机回复握手包表示一次地址分配成功，转至步骤2。（主机收到握手包则将Y-1）

需要说明的是，若在步骤1中生成了2个相同的最小随机数，将会出现2台“临时”主机，而从机接收到的校验码会出错，主机也无法收到从机回复的应答包。故约定主机发送地址分配命令后（与从机检测校验码出错同时），各设备定时2 s，2 s内各设备收不到主机的命令，将重新完成步骤1。

2.5 算法流程

上电启动后，各个设备遵循的算法流程如图2所示。

3 算法试验

本算法选用30台从机数进行仿真试验，记录每次生成的最小随机数xi即可得到自动分配地址所需的总时间T，即

图2 算法流程Fig.2 Algorithm flow chart

试验中，RS-485总线的波特率设置为9600 b/s，程序中设置Y=30，k=50ms，N=5；模M初始值选为101，Y 每减少 5，模 M 分别替换为 71，61，41，22，11。

试验选用2017年2月10日1～10号、2015年5月5日21～30号、2010年9月1日101～110号等3个批次的设备。机号n为1～30的设备，其中1～10号机的ID分别为07E1020A0001—07E1020A000A，11～20号机的ID分别为07DF05050015—07DF0505001E，21 ～30 号 机 的 设 备 ID 为07DA09010065—07DA0901006E。表2为具体的试验数据。

试验中，第1个最小的随机数是0，由17号机产生，因此17号机成为主机开始发送地址分配命令。试验未出现最小随机数相同的情况，表明a，b，M的选取适当。求得总时间T=7.95 s。

分别选取连续和完全随机的从机ID作为随机种子，各运行20次，均实现了自动组网及从机地址的自动分配，平均完成时间约8 s。另外，将本算法与采用随机时隙思想的方法进行对比，后者虽然也能实现地址的地址分配并避免地址冲突，但平均完成时间需要9 min，效率远低于基于随机数发生器的地址分配算法。由此可见，本算法具有执行效率高、稳定性好等优点。

表2 试验数据Tab.2 Experimental data

4 结语

本文为了解决基于总线通讯的无主机工控系统中自动组网与从机地址不方便设置的问题，提出了基于随机数发生器的自动组网与设备地址分配方法。对该算法进行了详细的分析，通过试验验证了该算法，并与其他地址自动分配算法对比，基于随机数发生器的算法所需时间更短，分配效率更高。实践证明，该算法对总线通讯网络是可行的。

[1] 马庆功，莫玉华，郑恩兴.基于RS485多机通信系统设计[J].电子世界，2012，33（1）：132-133.

[2] Tanenbaurn Andrew S.计算机网络[M].潘爱民，译.北京：清华大学出版社，2004.

[3] 杨自强，魏公毅.综述：产生伪随机数的若干新方法[J].数值计算与计算机应用学报，2001，22（3）：201-215.

[4] 林国顺，黄梯云.模拟随机数统计性质比较[J].数理统计与管理，2000，19（2）：30-34．

[5] 彭娜，黎英，林庆超，等.基于RS-485总线主从通信协议及其实现[J].云南大学学报（自然科学版），2007，29（s2）：259-262.

Automatic Allocation Method of Device Address Based on Random Number Generator

ZHANG Lei1，YANG Qi-fan2
（1.School of Electrical and Information Engineering，Jiangsu University，Zhenjiang 212013，China；2.Quality assurance department SAIC FAW-Volkswagen Automobile Co.，Ltd.，Shanghai 201800，China）

Bus communication is commonly used in industrial control systems，which is often a mainframe and a slave structure.The traditional bus communication network usually uses the manual method such as dialing code to set the address of the equipment.The automatic organization of the system and the automatic distribution of the address has always been a difficult problem.A new method of automatic network and device address allocation based on random number generator is proposed，which realizes the automatic distribution of the address.The method is applicable to the control system without host，which can automatically select the host，and can automatically organize and distribute the address on power supply，and the required time is shorter and the distribution efficiency is higher.Practice has proved that this method is stable and reliable，and has good application and popularization value.

bus communication；automatic networking；address allocation；random number

TP336

B

1001-9944（2017）11-0036-04

10.19557/j.cnki.1001-9944.2017.11.009

2017-06-05；

2017-09-03

张垒（1993—），男，在读硕士研究生，研究方向为控制工程。