Дата публикации: 30.04.2021
Master of Mechanical Engineering Taiyuan University of Technology
Wang Shi Ying
Professor of Mechanical Engineering Taiyuan University of Technology
In recent years, the automotive industry has become a pillar industry of the world, the role played by the automobile in the daily life and work has become increasingly prominent. In the car navigation retrieval system, whether from the perspective of retrieval speed, screen display, or memory management, it cannot meet the needs of users. In the design, the retrieval algorithm along the road of facilities retrieval can not only improve the retrieval system's modular structure, but also introduce the idea of thread pool. The whole system is divided into three modules: phenotype data structures; merging algorithm; B-Tree+. B-Tree+ and phenotype data structures being used can improve the search speed; a new road merging algorithm being proposed can improve the retrieval performance.
Retrieval algorithm along the road; thread pool; GPS; B-Tree+; Car Navigation Screen.
With the increase in the number of cars, people are coming to the concept of an ITC (Independent Transport Commission). In the transport department, the services of the information system, the control system, as well as electronics, are highly used. Thanks to modern technology, the relationship between the driver, the car and the track is getting better and better (p. 1; p. 2). The unified navigation can be navigated by the car's motion screen system at that moment on the road and this is the basis for a general navigation system. The 24-hour 3D GPS positioning of the vehicle offers vehicles the best way to get to the location. It has precise scheduling of road, path calculation speed, it can also be displayed on an electronic card and ensure a way launch. That gives customers a transport or nearby locations or hospitals and further data, about a given location, as well as show its position on the display. (p. 3).
The difficulty GPS on the marketplace is prominent representation is the information search system. The E-map and the facility search jointly called the information and search engine in the area of scientific studies and designs of GPS. It is executed via information folder retrieving, which is the purpose of retrieving the information folder. You need to use the services of public services, petrol services, inns and further services, as well as make a list, which is presented on the screen, so that you can get data regarding of the customers' locations. On the electronic chart, a file search and data analysis are requested, information about which is displayed on the screen at the end. Navigation data retrieval malfunction mostly has several aspects, such as: object information search velocity is too low; the information folder design inflexible, that’s makes it takes searching quite a lot; retrieval objects in real time may be achieved solely in the vehicle or at the direction of request features, features more subtle; electronic card display is very big, because of this, text distortion more deforms. (p. 4).
Materials and Methods
Object search we can search by classifications, such as, keyword search, Pinyin search, residence search, and others. The contrast between all types of search process exists in the implementation process and they are all almost the same. First, you need to receive the necessary data from the extraction device and then create a list of data indexing results based on the Index list; Secondly, you need to continue searching for the information list with the Index of the list that was filled in by the production and is important for getting search results; And the last one is when the user wants to know more detailed information, the program will update the search and show the information on the screen (p. 5).
Data retrieval system is the heart of car navigation system. Most noteworthy feature related on the data is retrieval system. The structure of the data retrieval presents on Fig1. These two modules of the facility retrieval and the E-map carried to the data retrieval system. To get a data file extraction, the search engines first finish parsing the data information, then make a list that will be displayed on the screen. Parsing data according to the classification of patterns of a multi-layer color screen, extracting data file is an electronic map.
Figure1. Structure of data retrieval system
A. Advanced Architecture Note
Layer01 are provided externally by all the functions of the NOTE. Layer02 interface works with the Layer01 functions and directs or opens the subordinate layer interface Layer02 includes functions like managing and scheduling notes and it's the only external interface. The process and operation of the note is the responsibility of Layer03. Layer03 shows the search-related functions and is responsible for all the processes that relate to the search. In NOTE Layer01 is located in the " top " Layer99 is a generic NOTE functional library that provides NOTE to another Layers and provides a operating process, a access of data process, an analytical function, a jump process and a ranking process.
The search engine is mainly called Note. NOTE applies a hierarchical module to make the code simple (p. 6). The NOTE consists of two parts, which includes different types of search and works with search, this is the first part. The next part deals with monitoring activities with the media. The first part is the user interface and it includes responsibilities for returning search responses and the API function. It is necessary to divide the NOTE into several parts so that each function is clear (Fig.2).
Figure2. NOTE structure before improvement
B. Improving the format of Data Search on the Road
Chinese plate consists of a fraction with the size of the square is 10 km. The grid ID is the center coordinates of the grid file and the unique identification of the grid files and grid base for extraction. The main drawbacks of the data warehouse are when traversing to position the grid and when searching for the corresponding grid, the filtering speed is very slow and the extraction speed is too slow. We use the B-tree and the phenotypic data structure to eliminate the warehouse disadvantage. B-Tree+ is the information warehouse tree of the index structure management. The phenotype works with information storage. In this case, the information can be obtained immediately and displayed on the screen with the search terms, as well as the search speed there is much faster.
Primarily, by applying blocks and sending, the information is stored as blocks. The grid file consists of 16*16 sets, then the set is divided into 8*8 blocks, each block consists of 32*32 sections.
Next, some information is stored with an index, the rest of all the parts are stored with each other. Services, such as, catering, shopping store, car, housing, sports, vehicles, education, culture, etc. are included in the category of road objects. The systematization includes a little group. The control piece of the data stores the size of the record from a file named PSHAREE.
Lastly, the received information file consists of 3 sections. The name of the text should separate all existing names in the file, because the name of the text is not exact and not fixed. Phone number, zip code, and details are also highlighted after the Area Code. For example, Taiyuan, the required information saved in PSHAREE 101, the name in NAMEE101. In a set of blocks, the name of the information blocks comes with numbers, such as, 16th block, blockset36 with the name block16. The information block of displacement is record in PSHAREE to storing extra data.
In general, to find the necessary information in the share folder, we must use the block folder; the share folder examines the name folder. The data store in Kiwi code is a designation for an object that can be used to filter the classification of the object; the coordinates of the place through which the car route is calculated are the distance. The data can be read in the information stored in the shared location folder. To find the phrase folders or the name folder, we use the Area Code.
C. Search Algorithm
Combining roads with a set of points is a set of points or a data module that extracts a note and a path that is responsible for the basis along the road. A road link joining along a road with criteria such as separately with another road with information about road intersections, an angle between 90 and 180 has requested permission from AutoNavi. The merger of the road through the angle is not perfect, because different attributes of the road can also be combined. In this scientific paper, we want to propose a new algorithm that is responsible for road attributes, this allows road attributes to combine and merge roads due to two intersecting road triangles. Express roads do not include roads such as, general, urban, or small streets, but include large highways such as, Highway 26, or expressways (p. 7; p. 8).
Results and Discussion
The judge for evaluating road attributes is used to determine the Pre-Express road and the Srh express road. If the path of the first segment is a highway or track, the first attribute of the judge of Pre-Espresso and Srh Express is equal to 1. If the path of the first segment is not a highway or track, the second attribute of the judge of Pre-Espress and Srh Express is equal to 0. If the forward is a vehicle segment, the Next Express is equal to 1. It is important to know the node of the current link - the first point, the next node - the last point. To connect roads, as in Figure 3, we get segment connections according to the new algorithm.
Figure3. Road merger diagram
Let's take point A as the lower-left corner, point B as the upper-right corner, and the center is the Radius. X ,Y direction is the file coordinate, which is the vertex of the lower corner of the blockleftX, blockleftY (Figure 4). SearchLeftALon, SearchLeftALat, SearchRightBLon, SearchRightBLat are vertex and the code for the XY coordinates of the direction of the block file. MeshLongitude =2588049000, MeshLatitude =122889000. MeshWidth=9217000, MeshHeight=6145000 (p. 9).
Figure4. Determine the search range
BlockLeftax = (SearchLeftaLon − MeshLongitude) / MeshWidth ;
BlockLeftay = (SearchLeftaLat − MeshLatitude ) / MeshHeight; (1)
BlockRightbx = (SearchRightbLon − MeshLongitude) / MeshWidth ;
BlockRightby = (SearchRightbLat − MeshLatitude ) / MeshHeight ;
BlockSetNo = Block _ x / BlkDivLon
Block _ y / BlkDivLat * BlkSetDivLon; (2)
BlockNo = (Block _ x%BlkDivLon)
(Block _ y%usBlkDivLat ) * BlkDivLon;
Defining the search range (Figure 4)
The algorithm for determining the distance of Parcel is shown below.
ParcelRangeax = (Locationa x − BlockRangeax) / ParcelW ;
ParcelRangeay = (Locationa y − BlockRangeay) / ParcelH ; (3)
ParcelRangeB ax = (Locationbx − BlockRangea x) / ParcelW ;
ParcelRangeBa y = (Locationby − BlockRangeay) / ParcelH ;
ParcelRangeax, ParcelRangeay is the number of upper-left blocks in the XY and the block was in the Mesh system of coordinates. ParcelRangebx, ParcelRangeby is the number of the upper-right block in the XY, respectively, when the block is in the grid system of coordinates. Locationax, Locationay, Locationbx, Locationby - this is the longitude and latitude of the allowed range of the plot separately. BlockRangeax, BlockRangeay is the longitude and latitude of the current block. ParcelWidth=289000, ParcelHeight=193000.
The search and result range is limited to certain quantities, such as five hundred meters, one thousand meters, five thousand meters, ten thousand meters, twenty thousand meters, and thirty thousand meters. For example, if we search for "hospitals", the search range first searches in the nearest five hundred meters, if it does not find it, the radius range is increased to a thousand meters, and so on. And if we need only 10 hospitals, and the search returns more, for example, 50, in this case, the algorithm is ranked by distance from the entire result and selects the nearest 10. In this way, the radius search reduces the range of the radius.
The radius = (20 (last radius)2)/(number of retrieval last time)
In this algorithm, there are two storage blocks; the first one stores the results temporarily in a storage called working memory. The second block is called the result memory and it can store two hundred records. This is good for GPS operation; meanwhile Layer01 can send grant requests on the screen. The main task of the search algorithm is to extract the results from the memory and deliver it to the user interface. How the algorithm works to search for results is shown in Figure 5. In this process, compiling an index is an important part. The result memory stores the contents of the index and outputs the list, and the working memory will be free.
Figure5. Retrieval time diagram
The search algorithm along the road searches for the entry and calculates the rectangle (we use the link path for the paragraph). For example, if the city is Taiyuan, let's take for example the size of 3.0 * 0.8 (km). Table1.
Table1. THE STATISTICS OF PARCEL RANGE IS DISPLAYED AS FOLLOWING
The algorithm for searching along the road in time takes 130 - 420 milliseconds. On average, ten links, takes a maximum search time of five seconds. Table2.
Table2. LINK NUMBER OF THE STATISTICS
Note: Car near the airport in Taiyuan. Optimizing the data format and radius leads to improved system performance.
In this scientific research paper, we investigated the search algorithm in the navigation system. To begin with, we had the whole system divided into several modules, such as, Layer 01, Layer 02, Layer 03, and Layer 99. The first layer works with the note and UI and is called as the front interface. The second layer is responsible for management and planning and is called the main interface. The next, third layer works with the search and label functions. Our last interface, the most important one, is responsible for noting the other interfaces, working with files, accessing data, navigation and ranking functions. And also with the help of the algorithm for searching along the road, we have significantly improved the speed of searching for results, which was the most important problem in our time.
In our new algorithm, we used a data structure using a B- tree and a tabular data structure. The B-tree is responsible for storing and managing the information index, and the tab is responsible for storing information and data, as well as increasing the search speed. Our merge algorithm puts forward a new idea, increases the search radius as well as the search speed. Generally speaking, the article presents the results of the performance analysis and the results of testing the algorithm, as a result, the new algorithm for searching along the road can achieve high efficiency and functions.
Broy, M. (2012). A Logical Basis for Modular Software and Systems Engineering. Theory and Practice of Informatics , 19-35.
D., B. P. (2010). Developing Real-Time System with UML, Objects, Frameworks and Patterns. China machine Press .
Guohui, L. (2019). Research on Vehicle Autonomous Navigation System. Harbin Unstitute of Technology , 92-103.
Huang Jing, Z. L. (2011). GPRS Traffic Statistic System on Android Platform. Computer Systems&Apllications , 141-143.
Hui Hu, Y. Y. (2013). GPS Receiver C/A Code Rapid Acquisition Technology Research. Journal of Information&Computational Science , 477-484.
Kewen, L. (2017). The FPGA Design in Vehicle Integrated Navigation System. Beijing University of Posts and Telecommunications , 80-98.
Limited, A. H. (2020). A road combined methods and merge device.
Lin Zhao, Z. Y. (2012). GPS/DR Vehicle Integrated Navigation System Based on Central Difference Kalman Filter. Journal of Information&Computational Science , 2771-2779.
S. Parsa, O. B. (2015). The Design and Implementation of Framework for Automatic Modularization of Software Systems. The Journal of Supercomputing , 71-94.
Shi Junyong, Z. X. (2011). Study and Implementation of Real-Time Traffic Information Navigation Terminal Based on GPRS. Computer Technology and Development , 171-174.
Xinqing, Y. (2017). Design and Implementation of Navigation System for Tourism Based on Android . Jilin University , 53-65.
Xu Shilong, L. B. (2015). Analis on High Sensitivy GPS Navigation Methods. Radio Engineering , 37-39.
Zheng Rui, C. J. (2019). New Algorithm of GPS Positioning in Incomplete Condition of Temporal Insufficient Signal. Journal of University of Electronic Science and Technology of China , 496-500.