EN中文

地球信息科学学报 >

2021 , Vol. 23 >Issue 8: 1422 - 1432

DOI: https://doi.org/10.12082/dqxxkx.2021.200690

地球信息科学理论与方法

基于格网化邻域查询的海上船舶救援搜索方法

  • 周为峰 , 1, * ,
  • 隋芯 1, 2 ,
  • 郭小天 1, 3 ,
  • 姜亚洲 1 ,
  • 程田天 1
展开
  • 1.中国水产科学研究院东海水产研究所,上海 200090
  • 2.上海海洋大学海洋科学学院,上海 201306
  • 3.浙江海洋大学信息工程学院,舟山 316022

周为峰（1978— ）,女,江苏高邮人,副研究员,从事空间信息技术在渔业上的应用研究。E-mail:

收稿日期: 2020-11-16

  要求修回日期: 2021-03-12

  网络出版日期: 2021-10-25

基金资助

国家重点研发计划项目(2019YFD0901405)

国家重点研发计划项目(2020YFD0901202)

中央级公益性科研院所基本科研业务费专项(东海水产研究所)(2019T03)

版权

版权所有,未经授权,不得转载、摘编本刊文章,不得使用本刊的版式设计。
收起

Searching Method for Marine Ship Rescue based on Grid Neighborhood Query

  • ZHOU Weifeng , 1, * ,
  • SUI Xin 1, 2 ,
  • GUO Xiaotian 1, 3 ,
  • JIANG Yazhou 1 ,
  • CHENG Tiantian 1
Expand
  • 1. East China Sea Fishery Research Institute, Chinese Academy of Fishery Sciences, Shanghai 200090, China
  • 2. College of Marine Sciences, Shanghai Ocean University, Shanghai 201306, China
  • 3. School of Information Engineering, Zhejiang Ocean University, Zhoushan 316022, China
* ZHOU Weifeng, E-mail:

Received date: 2020-11-16

  Request revised date: 2021-03-12

  Online published: 2021-10-25

Supported by

National Key R&D Program of China(2019YFD0901405)

National Key R&D Program of China(2020YFD0901202)

Special Research Fund for The National Non-profit Institutes(ECSFRI/CAFS)(2019T03)

Copyright

Copyright reserved © 2021
Fold

摘要

海洋渔业是高风险行业,各类海洋灾害频繁发生,海上航行、作业环境复杂,因此,海上快速救援对保护渔民的生命财产安全具有重要意义。本文基于空间剖分的格网化编码,提出一种根据有效救援距离和失事船舶位置进行邻域搜索以查找失事船只相邻和最邻近可供救援的船只的方法,其中有效救援距离通过救援船舶的类型和航速来设定,根据有效救援距离设置不同的编码搜索长度。本文将模拟实验区域设定为我国东海海域,随机生成1×104个船位点,在时间检索效率和内存占用两方面,实验结果表明,与传统的船舶间距离的计算方法相比,基于格网化邻域搜索的查询方法编码后船位数据较编码转换前船位数据占用内存空间减少56.47%,同时,编码后检索运算的用户时间是编码前用户时间的17.67%,因此,基于格网化邻域搜索的查询方法占用内存小,且运算效率较高,能够有效提升对遇险船舶邻域救援船只的查询效率。

关键词： 船舶救援; 有效救援距离; 格网化; 船位编码; 邻域搜索; 最邻近搜索; 时间效率比较; 内存占用

本文引用格式

周为峰 , 隋芯 , 郭小天 , 姜亚洲 , 程田天 . 基于格网化邻域查询的海上船舶救援搜索方法[J]. 地球信息科学学报, 2021 , 23(8) : 1422 -1432 . DOI: 10.12082/dqxxkx.2021.200690

Abstract

Marine fishery is a high-risk industry with various marine disasters occurring frequently. Furthermore, maritime navigation and operating environment are complicated. Therefore, rapid maritime rescue is of great significance to protect the life and property of fishermen. Based on the grid coding of spatial division, this paper proposes a method to search the neighborhood based on the effective rescue distance and the location of the wrecked ship to find the ships that are adjacent to the wrecked ship and the closest neighbor for rescue. The effective rescue distance is set by the type and speed of the rescue ship. Then, the different code search lengths are set according to the effective rescue distances. In this paper, East Sea is set as the simulation experiment area, within which 10 000 ship locations are randomly generated. In terms of time retrieval efficiency and memory occupation, the experimental results show that, compared with the traditional method of calculating the distances among ships, the memory space occupation by the ship position data after encoding conversion in our proposed method is 56.47% less than that before the encoding conversion. In the meantime, the user retrieval calculation time after encoding is only 17.67% of that before the encoding. Therefore, after the ship position is encoded, the proposed method occupies a smaller memory and has a higher computational efficiency, which can greatly improve the efficiency searching for rescue ships in the vicinity of the wrecked ship.

Key words： ship rescue; effective rescue distance; grid code; ship position code; neighborhood search; nearest neighbor search; time efficiency comparison; memory usage

1 引言

海洋渔业是高风险行业。海洋环境多变,海上极端性天气事件频繁发生。随着我国经济外向度的提升,我国近海航线日益密集,海上航行、作业环境日趋复杂[1]。与运输船相比,渔船的船体质量、装备水平和适航能力都有较大差距,抵御海洋自然灾害、防范交通和生产事故的能力都比较弱[2],发生渔船自沉、风损、触损、碰撞等各类海难事故的比例较高,给渔民的生命财产安全造成了严重威胁[3,4]。关于海上救援,已有的研究或者从具体的救援技术展开,如研究基于多无人机系统利用AI和边缘计算的方法进行海上搜索[5];或者从海上安全管理的角度探讨,优化海上搜救能力对策,并建议持续增加海上搜救力量以及扩大救援规模[6];或者从软件和硬件设计的改进入手,设计救援路线预报系统[7];或者从船舶互助组救援有效性检验的角度,通过计算船位间的距离找到适合被组内救助的船只总数占该编组中所有船舶总数的百分比[8]。2006年农业部制定的《渔业船舶水上安全突发事件应急预案》[9]中提到“应急救助按照就近救助原则”,且要积极引导渔民群众通过建立渔民社团、互助组织,提高船舶相互救助的能力。”由此可见,相邻船舶互救一直是船舶海难救助的第一选择。失事船舶距救援点越远,所需救援的时间越长,救援消耗的时间则越长,灾害损失越大。因此与失事船舶相邻的救援船只以最短的时间实施救援,可以有效降低人财物损失[10]。综合考虑施救能力以及参与救援的可能性,除了考虑距离失事船只最近的船舶实施救援以外,搜索一定有效救援距离范围内的船舶也十分必要[11,12]。如何快速搜索有效救援距离内的船只是船舶救援中最为重要的问题之一。已有的研究大多并没有直接从这一角度出发,即使考虑到船舶互助,也是通过计算船位间的欧氏距离来实现,需要将每个船位进行投影转换,然后利用经度和纬度的投影坐标计算两两之间的欧氏距离,然后进行距离比较。这一过程运算量大、时间长且占用内存资源较多。传统的地理信息系统通常使用基于树的索引（如二叉树、四叉树等）进行空间索引,但如果数据量很大,则操作成本高[13]。通过坐标编码转换和匹配一维字符串前缀选取数据的相关研究[14,15]表明,使用Geohash索引及HBase数据库进行大数据地图匹配,可以优化了数据匹配的性能,为灵活的周边查找和范围查找提供可能;亦有研究结合Geohash编码技术和神经网络对推荐出租车巡游路线进行研究,基于开放街道地图OpenStreetMap数据实现针对大规模出租车路网与轨迹数据的高效范围查询,提高了查询效率[16]。因此,为了改进海量船位数据对内存资源占用较大和查询符合救援条件的船舶时间效率较低的问题,本文从遇险船只（救援目标）的空间位置、可救援船舶至救援目标所需的航行时间入手,研究如何搜索和确定有效救援距离内的邻域以及最邻近的救援船舶,提出一种根据有效救援距离基于失事船舶位置进行邻域搜索查找失事船只相邻和最邻近可供救援的船只的方法,并在时间效率和内存占用两方面与已有的船舶间距离的计算方法进行比较,以期进一步提高救援实施的效率和有效性。

2 基于格网化的海上船舶救援方法

根据船舶救援需求（图1）,格网化的海上船舶救援工作主要分为以下4个步骤：① 船位数据的获取与格网化编码：通过北斗（或GPS）获取船舶位置的经纬度信息,并进行字符串编码;② 船位格网化编码的存储与获取失事船只的位置信息：使用关系型数据库存储格网化编码的船位,发生灾难时,失事船只通过短报文或VHF（甚高频电话）向陆地指挥中心报告位置信息[17];③ 失事船只的邻域救援船舶搜索：根据实际的救援方案设置不同范围的有效救援距离（D）,以此为基础进行对应的邻域格网化的救援船只搜索,以找出满足D的船只;④ 最邻近救援船只的查找：基于③ 中最小的D值,搜索最邻近救援船舶,通过八方向的邻域搜索找到距离失事船舶最邻近的船只,发送信号,请求最邻近船只实施救援,实现快速搜索符合救援条件的船只（图2）。
图1 海上失事船舶搜救一般流程

Fig. 1 General procedure for search and rescue of ship wrecked at sea

图2 格网化邻域查询的海上船舶救援搜索方法流程

Fig. 2 Flow chart of maritime ship rescue and search method based on grid neighborhood query

2.1 船舶数据的格网化编码

通过全球导航卫星定位系统获取船位的经纬度信息。参照Geohash的地理编码,以全球经纬度为编码范围,进行空间格网二分式剖分,对获取到的船舶位置信息进行编码,分别生成经度和纬度二进制编码,然后交叉组合生成统一的二进制编码,变成一维的字符串,为邻域搜索提供数据准备,步骤如下。
以经纬度(180° W, 90° S）点为编码的起点,依次地,对空间进行先纬向二分再经向二分：① 纬向上,上/北向空间设置编码为1,下/南向编码为0;经向上,将右/东向编码为1,将左/西向编码为0。把每次经纬二分称为一次剖分,即剖分深度为1,然后以相同的二分法对子区进行循环剖分;② 分别生成经度和纬度的二进制编码;③ 经度和纬度的编码按照二进制偶数位为经度编码、奇数位为纬度编码的方式,交叉组合生成统一的一维二进制编码;④ 将长一维的二进制编码以每5位二进制编码进行base32编码转换,获得最终的船位编码,为邻域搜索提供数据准备。本研究每次剖分以二分的子区左下角为起点,以相同的二分法循环剖分,将空间剖分到所需编码的范围大小,同一个格网的二进制编码具有相同的前缀[18,19]。根据其格网剖分原理,对北斗（或GPS）获取到的船舶位置信息进行编码,数据库中存储的船舶的经纬数据实现二维数向一维字符串转换,即用编码后的一维字符串来表示船舶的空间位置信息（图3）。
图3 格网化字符编码实现方法流程

Fig. 3 Flow chart of the realization method of grid character encoding

空间格网划分方法（图4）：
图4 格网化编码算法设计流程

Fig. 4 Flow chart of grid coding algorithm design

全球经纬度范围剖分后的网格数量可由式（1）表示：
Num = 2 2 n
式中：n代表剖分次数;Num(n)表示当剖分次数为 n时剖分形成的网格数量。
剖分后的格网大小可由式（2）表示：
R grid = 2 π R Num = 2 π R 2 2 n
式中：Rgrid代表剖分后格网的大小;R表示正球体半径（地球的参考椭球体近似的作为正球体处理,即R=椭球体半长轴a）,格网分辨率即格网所表示的实际区域的大小。
格网的剖分次数n与船位格网化编码长度length的关系为：
length = 2 n / 5
式中：n为剖分次数;length为编码长度。
为满足救援搜索邻域最近船只的精度需求,本研究将船位点的空间剖分次数/深度n设为20,空间距离小于20 m,所获得近似代替船位的8位格网化编码足够满足海上搜救需求,如对于船位点（125.94°E, 25.66°N）的编码为wu99cycp;船位点（126.08°E, 27.18°N）的编码为wucdmjb1。

2.2 船位格网化编码的存储与获取失事船只的位置信息

船位监控系统通过卫星导航定位获得船位的经纬度数据,同时对船位数据进行格网化编码。使用关系型数据库存储格网化编码的船位,即用一维编码来表示船舶的二维经纬度空间位置信息（表1）,并以此船位编码建立索引。
表1 邻域船位查询的数据库表结构

Tab. 1 Table structure of the database for neighborhood ship position query

表名 gridcode_vessels
列名 数据类型（精度范围） 空/非空 中文名称
name varchar(50) 非空 船名
id int 非空 船舶编号
time datetime 非空 船位数据发出时间
longitude float 非空 船舶经度
latitude float 非空 船舶纬度
speed float 非空 航速
direction char 空 航向
gridcode varchar(50) 非空 船位格网化编码
在数据库中建立字段（field）,分别为船名（name）、船舶编号,即唯一标识码（ID）、船位数据发出时间（time）、船舶经纬度（longitude,latitude）、航速（speed）、航向（direction）以及包含经纬度二维空间信息的船位格网化编码（gridcode）,基于北斗（或GPS）获取目标海域船舶的实时数据,编码后存储到数据库中,为快速搜索符合条件的救援船只提供数据支持。
当失事船只遇到紧急情况时,可通过北斗短报文[20]、VHF（甚高频电话）或其他无线通信方式向陆地救援指挥中心报告失事船舶位置信息。陆地救援指挥中心在得到失事船只的位置后,查找或计算其格网化编码。一般情况下,距离失事船只最近的船舶实施救援最有效,但是综合考虑救援效果、施救能力以及参与救援的可能性等方面,搜索有效救援距离内的备选船舶也十分必要。

2.3 失事船只的邻域救援船舶搜索

首先基于失事船舶的位置,根据实际的救援可能性设置不同范围的有效救援距离,以此为基础在数据库中搜索满足有效救援条件的邻近救援船只,陆地指挥中心再调度救援船只展开救援。
2.3.1 有效救援距离的确定
在搜索邻域救援船只时,需要先确定有效救援距离。有效救援距离,即当险情发生时,相邻其他船只能够对其施以有效救援行动的距离。有效救援距离通过船舶的航速及设定的有效救援时间的相乘计算得到。通过调查得知,我国渔船、非捕捞作业时航速范围为8~10节,快艇式救援船舶航速可达到25节（1节=1海里/h）,假设有效救援时间分别为2、5、10和24 h,通过式（4）计算得到的（表2）。
表2 不同类型船舶的有效救援距离计算

Tab. 2 Effective distances of different types of rescue vessels (km)

航速(海里/h) 救援时间/h
2 5 10 24
8(渔船、运输船) 28.8 72.0 144.0 345.6
9(渔船、运输船) 32.4 81.0 162.0 388.8
10(渔船、运输船) 36.0 90.0 180.0 432.0
25(快艇式救援船) 90.0 225.0 450.0 1080.0
D = v × t
邻域救援船只的搜索需要给定有效救援距离以确定编码的长度,码长越长,搜索的范围就越小。
2.3.2 对应有效救援距离的格网化编码长度的确定
根据表3,结合网格化编码,本研究的有效安全距离范围可设为3档,分别为D1=36 km,D2=90 km,D3=1080 km;满足有效救援距离D1、D2、D3对应的船位格网化编码长度分别对应的是编码前4位（length=4）、编码前3位（length=3）和2位（length=2）。编码相邻层级的格网之间为嵌套关系（表3、图5、图6）。
表3 编码长度、剖分次数及精度对应

Tab. 3 Correspondence table of code length, division times and accuracy

编码长度 剖分次数 格网大小/km 与有效救援距离的对应
1 1 2500
2 5 630 <D3
3 7.5 78 <D2
4 10 20 <D1
图5 空间位置与编码的嵌套关系

Fig. 5 Recursive relationship between spatial position and encoding

图6 不同编码长度与距离对应的关系

Fig. 6 Corresponding relationship between different code lengths and distances

2.3.3 基于不同救援距离的邻域船舶搜索与匹配
当根据所设置有效救援距离在船位数据库中进行邻近救援船只搜索时,搜索结果即满足条件的船只数量以集合的形式表示如下：
S ship , length = neighbor_search gridcode , Substr | Substr ship , length , neighborhood ≤ D , length ∈ 2,3 , 4 , D ∈ 1080,90,36
式中：ship是以船位格网化编码表示的失事待救援船舶的位置信息,即编码字符串;length为符合以ship为中心满足有效救援距离D搜索范围的编码长度;neighbor_search通过编码匹配在船位数据库中获得满足条件的船只集合,其中 gridcode 表示船位数据库中所有船只的格网化编码集合, Substr ( ship , length ) 为求解给定长度的编码字符的函数,将失事船只的ship前length位作为求解子串,在gridcode字符串集合中进行前缀匹配搜索;D为前述设定的有效救援距离,分别取值为 { 1080,90,36 } ,与之对应的编码长度length分别取值为 { 2,3 , 4 }。
整体过程为：通过匹配字符串前缀位数满足有效距离搜索条件。并将失事船只的船位编码作为主串（La）,救援船只的船位编码作为模式串（Lb）。
① 当有效距离查找范围设置为D3=1080 km时,待搜索邻域的条件为字符串前缀位数length=2,即La前2位与Lb前2位相同时,可获得与遇险船舶相距小于630 km的邻域救援船只S（length=2）; ② 当有效距离查找范围递进设置为D2=90 km时,待搜索邻域的条件为字符串前缀位数length=3,可以S（length=2）作为基础集合,在S（length=2）中查找满足前3位与La前3位相同的Lb,可获得与遇险船舶相距小于78 km的邻域救援船只S（length=3）;③ 当有效距离查找范围递进设置为D1=36 km时,待搜索邻域的条件为字符串前缀位数length=4,以S(length=3)作为数据集合,在S(length=3)中查找满足La前4位与Lb前4位相同的船位,可获得与遇险船舶相距小于20 km的邻域救援船只S（length=4）。可知,S(length=2)>S(length=3)>S(length=4)。

2.4 最邻近救援船只的查找

2.4.1 八邻域查找
除了根据有效救援距离搜索相邻近的船只外,还需进一步确定最近的可救援的船只。距失事船舶空间距离越近的船只,编码字符串前缀与失事船舶编码前缀的相似度越高,但当失事船只与最近救援船只分别处于不同格网的边界附近时,仅用匹配编码前缀的方法可能无法找到最邻近救援船只,因此,需进行八方向的邻域判断,找出距离失事船舶最邻近的救援船只,发送信号,请求救援,实现快速搜索符合救援条件的船只。
具体为：循环进行①增加编码字符匹配的长度length;②采用式（5）中的方法进行船位编码字符串匹配搜索;③直至 S ship , length 为空集时,根据船位的格网化编码进行八邻域搜索,查找最邻近的船舶。
根据 S ship , length 为空集时的编码长度length值来确定用于八邻域搜索的失事待救援ship船位编码的具体编码字符,以及该字符所在位的奇偶性（图7）。如length为奇数,即具体编码字符位于8位船位编码的奇数位,则根据奇数位邻域编码表查找八邻域,否则根据偶数位邻域编码表查找八邻域（表4—表5）。
图7 8位船位编码的奇偶图

Fig. 7 Parity map of 8-bit ship position encoding

表4 奇数位邻域编码表

Tab. 4 Odd-numbered neighborhood coding table

…
0 1 4 5 h j n p
… z b c f g u v y z b …
x 8 9 d e s t w x 8
r 2 3 6 7 k m q r 2
p 0 1 4 5 h j n p 0
b c f g u v y z
…
表5 偶数位邻域编码表

Tab. 5 Even-numbered neighborhood coding table

…
0 2 8 b
… z p r x z p …
y n q w y n
v j m t v j
u h k s u h
g 5 7 e g 5
f 4 6 d f 4
c 1 3 9 c 1
b 0 2 8 b 0
p r x z
…
采用式（5）中的方法进行船位编码的匹配和搜索,本文将集合S(ship, length)简写为S(length)。当船位编码的匹配过程所获得的集合S(length)为空集时,则对失事船舶ship的船位编码从左往右根据此时编码长度length来确定用于八邻域搜索的字符,并用该字符,根据length是奇数还是偶数来确定使用奇数位邻域编码表还是偶数位邻域编码表查找八邻域的字符：① 若任意奇、偶数表中第length位对应的字符位于非边界,则将失事船舶ship船位编码的前（length-1）位编码字符与查找到的八邻域字符组合;② 若表中第length位对应的字符位于边界,则求第（length-1）位对应字符周围同方向的相邻字符,如果第（length-1）位字符也处于边界则求第（length-2）位,以此类推,表示为（length-i）（0≤i≤length）,最终则将查找到的字符按照先后顺序进行拼接,确定失事船舶ship船位编码的八邻域对应的字符编码,获得八邻域的格网编码并进行式（5）中船位编码的匹配和搜索,查找最邻近的船舶。查找S(length)空集的循环步骤如下：
查找S(length)空集算法
For length<-5 to 8 by 1 /*图2中编码长度变量length循环起始值为5,循环最大值为8即船位编码长度,循环步长为1 */;
IF S(length) = ∅ /* 当S(length) 为空集,则跳出循环,输出本次循环length */;
THEN return length;
ELSE IF S(length) ≠ ∅ and length ≠8 /* 匹配查找后的集合 S(length)为非空且编码长度未至8*/;
THEN return( ) /*S(length)为非空,将结束本次条件判断,继续循环 */;
ELSE
return S(length) /* 此时,S(length) ≠ ∅,且满足 length=8,则将S(length)作为最终结果输出*/
End IF
End /*结束循环*/
2.4.2 查找八邻域的字符位于非边界时
假设以（127.1257°E, 28.3491°N）作为遇险船舶的经纬度坐标,其8位船位格网化编码为wv43kbf1,查找其最邻近船只。当船位的匹配查找结果S(length=5)为空集时,则根据length=5,前5位船位格网化编码为“wv43k”,可确定进行8邻域搜索的字符为k;length=5为奇数,字符k在编码中处于奇数位,且未处于边界,则采用奇数位邻域编码表进行邻域搜索;所搜索周围邻域即8邻域,分别为上、下、左、右、左上、右上、左下、右下,查找到的字符分别为"s" 、"h" 、"7"、 "m" 、"e" 、"t" 、"5"、 "j";将失事船舶ship船位编码的前（length-1）位编码字符,即前4位“wv43”与查找到的八邻域字符组合,获得的八邻域格网编码前5位分别是"wv43s"、"wv43h"、"wv437"、"wv43m" "wv43e"、"wv43t"、"wv435"、"wv43j",并以上述邻域的编码前缀位采用式（5）方法进行船位编码的匹配和搜索,查找最邻近的船舶,将符合条件的救援船只输出。最终找到编码前5位为“wv43t”的ID=8843,其为“wv43k”的最邻近船舶。
编码后的字符串除了代表某一经纬度值以外,还可以通过邻域编码表获取邻域船只的方向,如：“wv43t”位于“wv43k”的东北/右上方,即符合条件的ID=8843救援船舶位于失事船舶的东北/右上方（表6、表7）。
表6 wv43k邻域编码表

Tab. 6 wv43k neighborhood coding table

wv43e wv43s wv43t
wv437 wv43k wv43m
wv435 wv43h wv43j
表7 （127.1257°E, 28.3491°N）船只及邻域索引结果表

Tab. 7 (127.1257°E, 28.3491°N) Ship and neighborhood index results table

id gridcode longitude latitude
8843 wv43t 127.151 28.408
2.4.3 查找八邻域的字符位于边界时
若假设以（127.1257°E, 28.3491°N）作为遇险船舶的经纬度坐标,其8位船位格网化编码为wv43kbf1,查找其最邻近船只。当船位的匹配查找结果S(length=8)为空集时,则根据length=8,前8位船位格网化编码为“wv43kbf1”,可确定进行8邻域搜索的字符为“1”;length=8为偶数,“1”位于偶数位,且处于偶数表的边界,则采用偶数位邻域编码表（表5）进行邻域搜索,所搜索周围邻域即8邻域,分别为上、下、左、右、左上、右上、左下、右下,查找到的字符分别为"4" 、"0" 、"c"、 "3" 、"f" 、"6" 、"b"、 "2";由于“1”位于边界,则需对“1”的上一位（length=7）,即“f”,且位于奇数位,对其周围同方向的相邻字符查找,即“f”的左侧为“c”,所以对于“wv43kbf1”编码的左侧3个邻域（左、左上、左下）分为：“wv43kbcc”、“wv43kbcf”、“wv43kbcb”,其他5个方向（上、下、右、右上、右下）与非临界情况类似,分别为：“wv43kbf4”、“wv43kbf0”、“wv43kbf3”、“wv43kbf6”、“wv43kbf2”。

3 时间效率及内存占用分析

为验证本研究方法的性能,本研究使用R软件实现了基于格网化邻域船舶位置数据的搜救方法。实验数据以东海海域（23°00′N—33°10′ N,117°11′E—131°00′ E）为空间范围,模拟生成10 000条浮点型船舶位置数据,有效位数保留4位。实验环境为Windows10操作系统,2.40 GHz Intel Core(TM) i5 CPU,4G RAM,使用500 G 7200 RPM硬盘驱动器。
具体从内存占用和时间效率2个方面对比。
实验1：内存资源消耗对比试验。首先,计算10 000个浮点型船舶位置数据的内存占用大小,为保证船位数据的精度,以双精度浮点类型（double）的变量定义船舶的经纬度数据,此外,对于传统的方法通过欧氏距离计算两两经纬度点间的空间距离,也定义为double型数据,通过内存计算得出：经度、纬度及空间距离共3×104条数据,占用的内存空间为240 896个字节（Bytes）;对于格网化编码的数据,为满足船舶数据的精度要求,将经度和纬度数据分别进行20次格网剖分,字符串编码长度为8,空间分辨率为20 m,计算得到编码后的数据所占内存大小为104 856个字节（Bytes）（表8）。由此得出：格网编码降低了对内存资源的消耗,更加高效地利用内存资源。
表8 编码前后对比结果

Tab. 8 Comparison results before and after encoding

程序运行时间/s 内存占用/Byte
用户 系统 流逝
经纬度搜索 1.98 0.00 1.98 240 896
格网化编码搜索 0.35 0.04 0.52 104 856
船位及船位轨迹的存储一般是以经纬度二维数据直接存储在关系型数据库中,在经、纬度二维浮点型数据上进行查询和其他操作,相对于编码后的一维船位数据（一个字符串代表编码前的经度和纬度）存储空间占用较大,同时,根据实际需要,进行欧式距离计算,计算结果同为浮点型数据,而编码字符串等同于一个矩形区域,矩形的大小可表示为空间区域的大小,因此,在矩形区域内即可满足距离条件,无需计算两两之间欧氏距离并存储。
实验2：时间效率对比实验。本研究首先建立船位数据的数据库,导入实验数据,进行格网编码,再添加含有经纬度信息的船位数据,作为对比实验,查询时间是每种范围做100次查询的时间平均值。首先,求解基于经、纬度二维空间点两两之间的距离,并依次筛选出满足有效救援距离D1、D2和D3的船位点,通过调用R软件中proc.time( )函数,得出传统的欧式距离计算方法以及输出满足D条件的结果所用的时间,结果为：传统欧式距离计算方法中用户的运行时间为1.98 s,系统的运行时间为0.00s,流逝时间为1.98 s;对于格网化编码运算效率求解,同样通过调用R软件中proc.time( )函数,此时有效救援距离对应的替换为编码长度length（表3）,程序运行结果为：用户运行时间为0.35 s,系统运行时间为0.04 s,流逝时间为0.52 s,相对于编码前的运算时间用时较短（表8）。
由此可知,基于空间点的查询效率较低,单次查询所产生的时间消耗长,不利于搜索符合救援条件的船只[21]。本研究中根据编码字符串前缀的重合位数来搜索失事船只附近不同范围的救援船只,只需通过匹配字符串的前缀,大大降低算法的复杂度,同时,当船位点在格网的精度范围内发生变化时,编码结果不变,可使缓存查询效率提高,提高附近船只的查询速度,实现快速搜索符合条件的救援船舶以便后续展开救援。此外,根据救援需要进行不同范围搜索时,每次范围重新设定会将所有浮点型的船位距离数据重新遍历,导致计算机的运算效率不高且内存占用过大,降低船舶救援的时效性。

4 讨论

有效的海上搜救需要合理的救援调度方案和极高的时效性,其救援的速度与数据的获取、存储及处理的效率尤为相关。对海上遇险船舶进行救援需要重点考虑3个方面：遇险船只的空间位置（经、纬度信息）即救援目标、确定最邻近船舶或有效救援距离内的邻域救援船舶及各船舶至救援目标所需航行时间,其中最近或邻域船舶的搜索效率是影响救援的关键。已有的船舶互助有效性检验方法将每个船位进行投影转换,利用经度和纬度的投影坐标计算两两之间的欧氏距离,然后进行距离比较。相对而言,运算量大、时间长且占用内存资源较多。
在船舶位置的记录管理方面,现有的渔船监控系统（Vessel Monitoring System,VMS）直接将船位信息以经纬度二维数据进行存储管理[22],北斗的更新频率为3 min,即每隔3 min采样一次,记录渔船的动态特征数据[23],渔船捕捞状态持续数个小时,在不对位置信息进行优化的情形下,依据传统VMS存储的二维经纬度数据进行查询检索等计算机运算,其数据内存占用和磁盘存储空间占用是海量的。
在救援距离的考虑上,传统筛选满足救援条件的船位方法分为2个步骤：① 计算距离,距离计算是两两之间通过经纬度、地球半径、三角函数等进行欧氏距离求解,主要以乘法运算为主,计算机中乘法的运算速度比加、减法运算速度减少近10倍,而CPU进行位运算（与、或、非、异或）与加减法运算速度相当,因此,在运算方面欧式距离的计算相对较慢[24];② 距离比较,通过两两比较大小选出船与船之间的最短距离,然后判断得到的最短距离是否小于最远安全距离,最后判断某一船舶是否适合被组内其他船舶救助,筛选出符合要求的船位点,这个过程相较而言,计算过程复杂,运算复用性低,单次计算对内存消耗大。而用一维的字符串编码代替传统的二维经纬度,具有唯一性、一维性及递归性[25],在搜索周围邻近船舶时,无需计算欧氏距离,不需要存储用浮点型表示的距离数据,实现了将三维数据（经度、纬度、距离）用一维字符串的表示,减少对内存空间的占用。格网化编码不仅节省了内存资源,而且保留了空间信息,体现了地理学第一定律,即空间上距离相近的地物,在空间上具有相似的空间关系[26],即字符串前缀重合度越高,船舶空间距离越近;且单列（一维）索引效率明显高于多列（多维）,通过不断迭代细分,确保格网化编码字符串在某一范围内满足检索需求,提高数据处理效率,降低操作成本。本文的方法在数据的获取、传输中可以完全依托我国自主的北斗导航卫星及其RDSS终端实现,完全自主可控。

5 结论

本研究选取船位（127.13° E, 28.35° N）作为遇险船只,根据有效救援安全距离D1=36 km、D2=90 km、D3=1080 km确定编码长度,然而,剖分后的空间网格存在距离相近的船位点可能被划分在两个格网中,为防止附近救援船舶处于格网边缘的情况,本研究通过计算其周边相邻的8个格网编码,在查询结果中进行二次过滤,以解决船位格网边缘且最邻近的问题,进而实现最邻近船舶的搜索。此外,通过对二进制编码后的经纬度数据分析可知,字符串的奇、偶数位的排列规则不同,对应的排列方式也不同（表4、表5）。
算法性能比较中,通过时间效率和内存占用两方面进行对比。在时间效率上,引入计算机操作系统中的运算时间的概念：“用户”是消耗在应用程序（非操作系统部分）执行的时间,“系统”是底层操作系统执行（例如磁盘读写等）部分的时间,“流逝”是经过的总时间（可以认为是前二者的总和）,一般优化时主要关注“用户”的时间[27],实验结果表明,编码后检索运算的用户时间是编码前用户时间的17.67%。在内存消耗方面,格网编码降低了对内存资源的消耗,更加高效地利用内存资源。实验结果表明,与传统的船舶间距离的计算方法相比,编码后船位数据占用内存较编码转换前船位数据占用内存空间减少56.47%,因此,本文提出的方法便于海量海洋船舶信息的存储和管理,并在船舶搜救中可快速计算,以提高救援速度及效率,保护渔民生命财产安全。
综上所述,时间是有效救援的根本意义,相比于电子海图人工目视的解读,使用编码字符串进行救援船舶的搜索,确定有效救援船舶的搜索结果更为客观和精准;用编码字符串进行救援船舶的搜索,程序运行时间较短、占用内存空间小,是一种邻域救援船舶搜索的高效算法。未来,要进一步比较在计算过程中对内存资源的消耗情况（如响应时间、吞吐量）以及远洋船位数据的搜索效率,支持全面、大范围的查找,使索引更好地适用于实际应用。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
钟碧良. VTSAIS信息环境下船舶救援信息系统初步研究[J]. 广州航海高等专科学校学报, 2011, 19(4):8-10.

[Zhong B L. Preliminary study for the VTSAIS under the environment information system[J]. Journal of Guangzhou Maritime College, 2011, 19(4):8-10. ]

[2]
黄锦鹏. 国际海上避碰规则与我国渔船现状的矛盾分析与探讨[J]. 南通航运职业技术学院学报, 2010, 9(1):40-45.

[Huang J P. Probe into inconformity of regulatory clauses to the current situation of Chinese fishing vessels[J]. Journal of Nantong Vocational & Technical Shipping College, 2010, 9(1):40-45. ]

[3]
董加伟. 渔业海难救助困境解析[J]. 大连海事大学学报(社会科学版), 2014, 13(6):57-61.

[Dong J W. Analysis of the dilemma of fishery shipwreck rescue[J]. Journal of Dalian Maritime University (Social Sciences Edition), 2014, 13(6):57-61. ]

[4]
杨丽. 近海捕捞船舶海上突发事故多元化主体救助研究[D]. 青岛:中国海洋大学, 2015.

[Yang L. Research on the diversification rescue subjects of maritime accidents about inshore fishing boats[D]. Qingdao: Ocean University of China, 2015. ]

[5]
Queralta J P, Raitoharju J, Gia T N, et al. AutoSOS: Towards multi-UAV systems supporting maritime search and rescue with lightweight AI and edge computing[J]. arXiv preprint arXiv, 2005.03409,, 2020.

[6]
李志亮, 刘虎, 艾万政. 舟山海上搜救现状及对策[J]. 水运管理, 2018, 40(3):28-29,33.

[Li Z L, Liu H, Ai W Z. Current situation and countermeasures of maritime search and rescue in Zhoushan[J]. Shipping Management, 2018, 40(3):28-29,33. ]

[7]
孙茂金, 吕靖. 基于动态GIS的救援船舶海上航行路线精准预报系统[J]. 舰船科学技术, 2018, 40(16):37-39.

[Sun M J, Lv J. Accurate prediction system for rescue ship's sea route based on dynamic GIS[J]. Ship Science and Technology, 2018, 40(16):37-39. ]

[8]
中国水产科学研究院东海水产研究所. 一种基于轨迹聚类的船舶互助组救援有效性检验方法[P]. 中国专利:ZL2014 10686666.7, 2017-04-26.

[East China Sea Fishery Research Institute, Chinese Academy of Fishery Sciences. Ship mutual-aid team rescue validity testing method based on track cluster[P]. Chinese Patent: ZL2014 10686666.7, 2017-04-26. ]

[9]
农业部. 渔业船舶水上安全突发事件应急预案[N]. 中国渔业报, 2006-8-7(002).

[Ministry of Agriculture. Emergency plan for fishery vessels water safety emergency[N]. China Fishery Newspaper, 2006-8-7(002). ]

[10]
杨东霞. 海上突发事故应急船舶优选与调度研究[D]. 秦皇岛:燕山大学, 2013.

[Yang D X. Study on optimization and scheduling of marine accident emergency[D]. Qin Huangdao: Yanshan University, 2013. ]

[11]
崔迪, 张华. 基于马尔科夫链的溢油事故应急救援船舶调度问题研究[J]. 中国水运, 2013, 13(3):24-25.

[Cui D, Zhang H. Research on ship dispatching problem of oil spill accident emergency rescue based on Markov chain[J]. China Water Transport, 2013, 13(3):24-25. ]

[12]
周国平. 海上救助历史沿革与海洋救助船技术发展综述[J]. 船舶设计通讯, 2014(增2):16-20.

[Zhou G P. The Overview of ocean salvage history evolution and ocean rescue ship technology development[J]. Journal of Ship Design, 2014(Add 2):16-20. ]

[13]
Van L H, Takasu A. An Efficient Distributed Index for Geospatial Databases[J]. Lecture Notes in Computer Science, 2015, 9261:28-42.

[14]
Cho W, Choi E. A basis of spatial big data analysis with map-matching system[J]. Cluster Computing, 2017, 20(3):2177-2192.

DOI

[15]
赵雨琪, 牟乃夏, 祝帅兵, 等. 基于GeoHash算法的周边查询应用研究[J]. 软件导刊, 2016, 15(6):16-18.

[Zhao Y Q, Mou N X, Zhu Sh B, et al. Research on application of peripheral query based on Geohash algorithm[J]. Software Guide, 2016, 15(6):16-18. ]

[16]
栾方军, 张鹏旭, 曹科研. Geohash编码在出租车巡游路线推荐中的应用[J]. 计算机与数字工程, 2020, 48(12):2836-2842.

[Luan F J, Zhang P X, Cao K Y. Application of geohash coding in taxi cruise route recommendation[J]. Computer & Digital Engineering, 2020, 48(12):2836-2842. ]

[17]
耿虎. 现代通信技术在船舶及其救援中的应用[D]. 舟山:浙江海洋大学, 2017.

[Geng H. The application of modern communication technology in ship and its rescue[D]. Zhoushan City: Zhejiang Ocean University, 2017. ]

[18]
向隆刚, 王德浩, 龚健雅. 大规模轨迹数据的Geohash编码组织及高效范围查询[J]. 武汉大学学报·信息科学版, 2017, 42(1):21-27.

[Xiang L G, Wang D H, Gong J Y. Organization and efficient range query of large trajectory data based on geohash[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1):21-27. ]

[19]
邢凯, 罗永龙, 宁雪莉, 等. 基于Geohash编码的位置隐私保护算法[J]. 计算机工程与应用, 2019, 55(1):96-102.

[Xing K, Luo Y L, Ning X L, et al. Location privacy protection algorithm based on geohash encoding[J]. Computer Engineering and Applications, 2019, 55(1):96-102. ]

[20]
中国水产科学研究院东海水产研究所. 基于位置的海洋渔业信息服务方法[P]. 中国专利:ZL2012 1 0332536.4, 2014-09-24.

[East China Sea Fishery Research Institute, Chinese Academy of Fishery Sciences. Position-based marine fishery information serving method[P]. Chinese Patent: ZL2012 1 0332536.4, 2014-09-24. ]

[21]
王翔, 杨国东. 基于Geohash 的出租车汽车轨迹的存储与应用研究[J]. 科技资讯, 2015, 35:69-71.

[Wang X, Yang G D. Research on storage and application of taxi car trajectory based on Geohash[J]. Science & Technology Information, 2015, 35:69-71. ]

[22]
周为峰, 陈雪忠, 樊伟, 等. 基于位置的信息服务在海洋渔业中的应用与展望[J]. 世界科技研究与发展, 2015, 37(5):611-617.

[Zhou W F, Chen X Z, Fan W, et al. Location-based information service's applications and it's prospects in marine fisheries[J]. World Sci-Tech R & D, 2015, 37(5):611-617. ]

[23]
中国卫星导航系统管理办公室. BD 420006—2015 北斗/全球卫星导航系统(GNSS)定时单元性能要求及测试方法[S]. 2015.

[China Satellite Navigation Office. BD 420006-2015 Beidou/GNSS timing unit performance requirements and test methods[S]. 2015. ]

[24]
王诚, 刘卫东, 宋佳兴. 计算机组成和设计[M]. 杭州: 浙江大学出版社出版, 2004.

[Wang C, Liu W D, Song J X. Computer organization and design[M]. Zhejiang Province: Zhejiang University Publishing, 2004. ]

[25]
Haroun A, Mostefaoui A, Dessables F. Data fusion in automotive applications[J]. Pers Ubiquit Comput, 2017, 21:443-455.

DOI

[26]
Ben Brahim M, Drira W, Filali F, et al. Spatial data extension for Cassandra NoSQL database[J]. Journal of Big Data, 2016, 3(1):1-16.

DOI

[27]
王小宁, 刘撷芯, 黄俊文, 等. R语言实战(第2版)[M]. 北京: 人民邮电出版社, 2016.

[Wang X N, Liu X X, Huang J W, et al. R in action data analysis and graphics with R (second edition)[M]. Beijing: Posts & Telecom Press, 2016. ]

Options
文章导航

/

〈 〉