一 种 简 单 的 自组 织 多 跳 路 由算 法 设 计 徐 世 武 ，王 平 ，江 华 丽 ，何 花 (福 建 师 范 大 学 物 理 与 光 电信 息 科 技 学 院 ，福 州 350007) 摘 要 ：简要 阐述 传 感 器 网络 节 点 的 基 本 体 系结 构 ，重 点 介 绍 基 于 单 片 机 ATmega128L和 CC2420的 ZigBee传 感 器 节 点 的硬 件 设 计 ，并在 此 硬 件 平 台上 ，设 计 了一 种 多跳 自组 式路 由协 议 ，用硬 件 进 行 组 网 ，验 证 了该 路 由协 议 的 可 行 性 。 关 键 词 ：ZigBee传 感 器 节 点 ；ATmega128L；CC242O；路 由 协 议 中 图分 类 号 ：TP368．1 文献 标 识 码 ：A A Sim ple Self—organizing M ulti-hop Routing Algorithm Xu Shiwu，W ang Ping，Jiang Huali，He Hua (School of Physics and 0ptoekctronics Technology，Fujian Normal University，Fuzhou 350007，China) Abstract：The basic architecture of sensor network node is described，and the hardw are design of the ZigBee sensor nodes based on AT m ega128L and CC2420 are introduced． A self organizing routing protocol is designed based on this hardw are platform ． T hrough networ king experim ents， the feasibility of the protocol is verified． Key w ords： ZigBee node； AT m egal 28L ；CC2420；routing protocol 无 线 传 感 器 网 络 集 成 了 传 感 器 技 术 、计 算 机 技 术 和 通 间 长 和传 输 率 要 求 不 信 技 术 ，在 军 事 、环 境 、健 康 、家 庭 、商 业 等 许 多 方 面 有 着 巨 高 等 特 点 ，选 择 AVR 大 的潜 在 应 用前 景 … 。无 线 传 感 器 网 络 由 大 量 密 集 分 布 单 片 机 ATm egal28L 的传 感 器 节 点通 过 自组 织 的 方 式 形 成 网 络 ，节 点 通 过 网 络 协 议 快 速 形 成 自主 构 建 、自主 组 织 和 自 主 管 理 的 通 信 网 处 理 器 作 为 本 设 计 的 处 理 器 。 它 与 一 般 的 络 。这 种 数 千 个 微 小 的 节 点 之 间互 相 通 信 、通 过 接 力 的 方 法 实 现 大 范 围监 控 的 模 式 极 大 地 提 高 了 工 作 效 率 。 8位 机 相 比 ，具 有 高 性 能 、高 速 度 、低 功 耗 图 1 无线传感器节点基本组成 由 于传 感 节 点 一 般 布 置 在 人 员 较 难 到 达 的地 方 ，更 换 和 硬 件 资 源 丰 富 的 特 点 ]。 节 点 较 难 。 当 某个 路 由节 点 因 电池 耗 尽 等 原 因而 损 坏 ，则 1．2 通 信 模 块 该 路 由节 点 的子 节 点 将 脱 离 网络 ，造 成 较 大 损 失 。本 文 基 CC2420是 Chipcon公 司 开 发 的 一 款 低 功 耗 通 信 芯 于 此 情 况 设 计 一 种 路 由协 议 ，使 损 坏 的路 由 节 点 的 子 节 点 通 过 自组 织 的 方 式 重 新 加 人 网络 ，减 少 损 失 。 片 。 由 于 其 唤 醒 时 延 短 ，使 得 它 能 有 更 多 的 时 间 处 于 睡 眠 状 态 ，从 而 大 大 降 低 了节 点 的能 耗 ，延 长 节 点 的 寿 命 。E4] 1 节 点 硬 件 平 台 传 感 器 节 点 是 构 成 无 线 传 感 网 络 的 基 本 平 台 ，具 有 传 统 网络 的终 端 和 路 由 的双 重 功 能 ：一 方 面 要 实 现 数 据 的 采 集 和处 理 ；另 一 方 面 还 要 对 其 他 节 点 转 发 的 数 据 进 行 存 储 、管 理 和融 合 等 处 理 。 虽 然 其 设 计 不 一 ，但 是 基 本 结 构 相 同 ，一 般 由 传 感 器 模 块 、处 理 器 模 块 、无 线 通 信 模 块 和 能 量 供 应 模 块 组 成 ]。基 本 组 成 如 图 1所 示 。 1．1 OPU 处 理 器 部 分 1．3 ATmegal28L与 002420的 硬 件 连 接 口 CC242O与 ATmega 128I 的 连 接 如 图 2所 示 。 CC2420 与 处 理 器 的 连 接 比较 简 便 ，它 使 用 SFD、FIFO、FIFOP 和 CCA 四 个 引脚 表 示 收 发 数 据 的 状 态 ；处 理 器 ATmega 128I 通 过 SPI接 口 (CSn、SO、SI、SCLK)与 CC2420交 FIFO PB7 PD7 PD 6 FIF0P C CA SFD CSn SS PD 4 SI M 0SI S0 M ISO SCLK SCLK 换 数 据 、发 送 命 令 ，通 过 VREG— RESET N VREG EN PA6 PA5 EN 和 RESET N两 个 引 脚 实 现对 作 为 一 般 采 集 数 据 的节 点 ，考 虑 节 点 数 量 多 、待 机 时 CC2420的使 能 和 复 位 ，使 其 产 生 128L的 连 接 paper@mesnet．corn．cn(投稿专用) Micr。c。ntroIlers＆Embedded Systems 1 5 

CC2420所 需 的 1．8 V 电压 ，从 而使 CC2420进 入 正 常 工作 广 播 A 节 点 发 出 的 信 的 状 态 。 2 自 组 织 路 由协 议 设 计 2．1 节 点地 址 的分 配 在 网络 中每 一 个 父 设 备 都 有 一 个 有 限 的 网络 地 址 子 块 ，这 些地 址 在 特 定 的 网 络 中是 唯 一 的 ，合 理 地 分 配 节 点 的地 址 ，对 减 少 父 设 备 不 必 要 的 地址 浪 费 至关 重 要 。本 设 计 中采 用 了分 布 式 地 址 分 配 机 制 ，协 调 器 决 定 了 网络 中 的 最 多 子 设 备 数 和 子设 备 的最 大 的路 由器 数 目，同时 还 决 定 息 ，当 它 们 收 到 子 节 点 的 响 应 信 息 时更 新 自己 的 路 由 表 ，D、E 两 个 节 点 收 到 A 节 点 发 出 的 信 息 时 ，定 义 自身 的 路 由深 度 为 2。其 中 5个 节 点 组 成 的路 由表 如 表 2所 列 。 图 3 节 点 的 组 网 及通 信 范 围 表 2 节 点 组成 的路 由表 了 网络 的最 大 深 度 。路 由器 的最 大 个 数 由 NIP属 性 nwk— 节 点 编 号 节点 路 由跳 数 上 一 级 节 点 同级 节 点 下 一 级 节 点 MaxRouters确 定 ，其 余 的 为 终 端 设 备 。协 调 器 本 身 的 连 接深度为 0，它 的子设备的连接深度为 1，子设备 的子设 备 连 接 深度 为 2，以次 类 推 递 增 。 假 如父 设 备 能 够 拥 有 的 子 设 备 的 数 量 最 大 值 为 nwk— MaxChildren(C )，网 络 的 最 大 深 度 为 nwkMaxDepth (L )，子设 备 中允 许 路 由器 的最 大 个 数 为 nwkMaxRouter (R )，则 函数 Cskip(d)是 父 设 备 所 拥 有 的 地 址 数 ，Cskip (d)的计 算 如 下 ]： 1+ C ·(L 一 d 1) ，R 一 1 Cskip(d)一{ ± 二垦 二 ：垦 ：：： I 1 R — m , Rm=／=l A B C D E O 1 1 2 2 无 A A B C 无 C B E D B、C D 、E E、D 无 无 节 点 在 自组 织 的 过 程 中 ，某 节 点 可 能 会 收 到 同级 节 点 ，或 其 他 不 同 级 节 点 的路 由广 播 请 求 ，这 时 该 节 点 可 以 选 择路 由 跳数 最 小 的路 径 ，然 后 更 新 自己 的路 由表 。本 设 计 中 A、B、c三 个 节 点 负 责 路 由 表 的建 立 与 维 护 ，主 要 包 括 目的地 址 、状 态 、下 一 跳 地 址 等 。 路 由表 结 构 体 定 义 如 下 所 示 ： typedef struc R0UTIN( ENTRY( 如果 一 个 设 备 的 Cskip(d)的值 为 0，则 该 设 备 为 终 端 设 备 ，没 有 地 址 分 配 能 力 。如 果 设 备 Cskip(d)的 值 大 于 SH 0 RT — ADDR destAddress；／／目 的 地 址 ROU T E— STATUS status； ／／状 态 0，可 以为 子 设 备 分 配 地 址 ，如 果 子 设 备 是 路 由器 ，则 可 以 SH OR T — ADDR nextHop； ／／下 一 跳 地址 为 它分 配 一 组 地 址 ；如 果 为终 端 设 备 则 分 配 一 个 唯 一 的 地 )ROUTING—ENTRY ； 址 。通 过 一个 连续分 配 的 方 式 ，网 络 地 址 A 将 被 分 配 到 其 中节 点 的邻 居 记 录表 定 义 如 下 所 示 ： 第 n个 地 址 终端 设 备 ，根 据 式 (2)进 行分 配 ： typedeI struct NEIGH BOR — — RECORD{ A 一 A 。 + Cskip(d) ·R + n，1《 n《 (C R ) LON G— ADDR longAddr； ／／扩 展 地 址 (2) SHORT_ADDR shortAddr；／／网络 地址 本 设 计 中采 用 了 5个 节 点 ，分 别 记 号 为 A、B、C、D、E。 其 中 A 号 节点 作 为 协 调 器 与 主 机 相 连 ，B、C号 两 个 节 点 作 为路 由节 点 ，D、E号 两 个 节 点 作 为 终端 节 点 。 SHORT_ADDR panID ／／PAN标 识 符 BYTE LogicalChannel； ／／逻 辑 信 道 NEIG H BO R— ． RECORD— DEVICE— — IN FO devicelnfo )NEIGHBOR RECORD； ／／15字 节 typedef union — N EIGH BOR— RECORD_ DEVICEl_INFO( 表 1 节 点 的地 址 偏 移 量 网络 深 度 d 偏 移 量 值 Cskip(d) struct{ 即 C 一 2，R 一 2，L 一 2。则 根 据 式 (1) 计 算 出 来 的 Cskip (d)值 如表 1所 列 。 2．2 节 点 组 网 路 0(A) 1(B C) 2(D E ) 3 1 O A、B、C、D、E节 点 的组 网及 通 信 范 围 如 图 3所 示 。A 节 点 通 过 使 用 NLDE—DATA．request原 语 ，并 设 置 Ds— tAddr参 数 为 0xffff(广 播 网 络 地 址 )广 播 形 式 发 送 自组 织 命 令 ，并定 义 自身 路 由深 度 为 0。B、C两个 节 点 收 到 A节 BYTE LQI：8； ／／RF传输 链 路 质 量 的 平均 值 BYTE Depth ：4； ／／邻 居设 备 的树 状 深 度 BYTE StackProfile：4； ／／ZigBee协 议 栈 标 志 BYTE ZigBeeVersion ：4；／／用 于 网络 发 现 BYTE deviceType：2； ／／设 备 类 型 BYTE Relationship：2；／／邻 居设 备 与 当前设 备 之 间 的关 系 BYTE RxOnW henIdle ： 1； ／／表示 邻 居 设 备 接 收 机 在超 帧 活 动期 的 空 闲是 否工 作 点 的 广播 请 求 后 ，分 别 向 A 节 点 返 回 响 应 信 息 ，并 把 自 己 BYTE PermitJoining ：1； 的 路 由深 度 定 义 为 1。然 后 ，B、C两 个 节 点 以 同样 的 方 式 ／／表 示邻 居设 备 是 否 正 在 接 收连 接 请 求 1 6 《平‘}机乌嵌入式条惋应冈》_圈匝_田豳圈岫 adv@mesnet，corn，en(广告专用) 

BY TE PotentialParent ： 1； 道 等 待 信 标 请 求 帧 等 。 当对 B、C路 由节 点 和 D、E终 端 节 ／／表示 是否 将 连 接 失 败 的 邻 居 设 备 设 置 为 潜 在 的父 设 备 点 打 开 或 关 闭 其 中某 些 节 点 ，串 口调 试 助 手 将 会 显 示 各 个 )bits； DW 0R D Val； )NEIGHB0R— REC0 RD DEV ICE IN F0 ； — — typedef struet— N EIG H B0R— T ABLE— INF0 { BYTE depth； BYTE cSkip； ／／网络 的深 度 ／／地 址 块 大 小 SH ORT_ ADDR nextEndDeviceAddr；／／给 下 一 终端 设 备 地 址 SH ORT _ ADDR nextRouterAddr； ／／给 下 一 路 由设 备 地 址 BYTE numChildren； ／／拥 有 孩 子 数 BYTE numChildRouters； ／／路 由器 个 数 节 点 的 不 同信 息 。 主要 信 息 是 收 、发 信 标 帧 ，以及 网 络 中 路 由个 数 、孩 子 个 数 ，并 为 网络 中各 个 节 点 动 态 地 分 配 地 址 等 。 3 结 论 本 文 设 计 的 节 点 功 耗 较 低 ，可 靠 性 好 ，体 积 较 小 ，集 成 度 较 高 ；无 线 通 信 模 块 独 立 开 来 ，多 层 布 线 ，减 小 了 干 扰 ， 增 大 了 传 输 距 离 。还 可 以 根 据 实 际 的 需 要 更 换 不 同 的传 感 器 模 块 。本 文 的 创 新 在 于 构 造 一 种 简 单 的 自组 式 多 跳 BYTE numNeighbors； ／／邻 居 表 设 备 个 数 路 由设 计 ，该 协 议 结 构 简单 ，实 现 容 易 ，而 且 采 用 了分 布 式 )NEIGHBOR— TA BI E— IN FO ； 地 址 分 配 ，节 点 设 备 不 必 保 存 占 用 庞 大 内存 的路 由表 ，最 2．3 节 点 申请 加 入 网络 的 流 程 小 化 网 络 流 量 ，减 少 父 设 备 不 必 要 的 地 址 浪 费 ，非 常 适 合 节 点 申请 加 入 网络 程 序 流 程 图 如 图 4所 示 。 小 型无 线 传 感 器 网络 。I 参 考 文 献 [1]任 丰 原 ，黄 海 宁 ，林 闯 ．无 线 传 感 器 网 络 [J]．软 件 学 报 ，2003， 14(7)：1282—1291． [2]宋 文 主 ．无 线 传 感 器 网络 技 术 与 应 用 [M]．北 京 ：电 子 工 业 出 版 社 ，2007：128—144． I-3]马潮 ．高 档 8位 单 片 机 ATmega128原 理 与 开 发 应 用 指 南 [M]．北 京 ：清 华 大 学 出版 社 ，2004：63—66． [4]ChipCon．SmartRF CC2420 Datasheet(rev 1．3)，2005—10 — 03． [53吕治 安．ZigBee网 络 原 理 与 应 用 开 发 [M ]．北 京 ：北 京 航 空 航 天 大 学 出版 社 ，2008：119—140． 徐世 裁 《须 螯 研 究筵 》，研 宪 磐 翻 舞 嵌入 裁 辘 惹 线 臻 感 器 糍络 王 平《高级工程师)’研究领域为嵌入式系统 通信网络新技术、无线书} 感器网络 江华丽(硕士研究生)，研究方 为 信息处理与多媒体、通 信与信息系统等 何花(硕士研究生)’研究方向为嵌入式系统、网络 图 4 节 点 申 请 加 入 网 络 程 序 流 程 2．4 串 口 调 试 助 手 分 析 结 果 将 A 节 点 与 PC机 相 连 ，打 开 A 节 点 ，串 口调 式 助 手 打 印 的 信 息 包 括 网 络 最 大 深 度 I ，节 点 可 容 纳 最 多 Router数 R ，节 点 可 容 纳 最 多 孩 子 数 C ，以 及 在 哪 个 信 一叠 一 (收修改稿j日期j2o… m 参 考 文 献 [1]Cadence design system[OL]．(2005—07—24)[2010—05 ． http t I{w ．cadence．corn／Training／Pages／cdsdoc．aspx． [2]周 润 景 ．Cadence高 速 电路 板 设 计 与 仿 真 [M]．北 京 ：电 子 工 信 技 术 ，2004，30(6)：25． [5]陈 旭 ，宋 利 权 ，斐 霞 ．运 用 SPECCTRAQUest实 现 高 速 图 像 处 理 电路 设 计 口]．电子 设 计 与 应 用 ，2004(9)：82． [6]张 汝 金 ，刘 琨 ．基 于 Cadence的 高 速 PCB设 计 [J]．西 南 民 族 大 学 学 报 ：自然 科 学 版 ，2004，30(6)：813． 业 出版 社 ，2008：472． — 一 。 _ 一 0 - ll … * ll i粱龙《硕士研 究生) 要 研豢 向 组织 缮 ◇ 技术等蓄垂 I-3]Altera．Nios II Processor Reference Handbook，2007． [4]黄 进 燕 ．基 于 Cadence软 件 的高 速 SDRAM 设 计 [J]．无 线 通 薯 薯 曩 薏 i董 ? 董 j l i paper@mesnet．corn．on(投稿专用) Mic 。c。nt 。11ers&Embedd d Sy。tems 1 7