Abstract:
A compression method featuring dynamic coding for wireless communication in wireless network is used to transmit a packet to clients. An access point (AP) divides a packet into several chunks all having a fixed length, sorts repetition frequencies of all the chunks, and encodes the repeated chunks with Huffman codes. Before transmitting the packet, AP divides the packet into chunks and determines whether there are chunks having been encoded, and transmits the encoded packet and the codes thereof to a specified client and other clients within coverage of transmission. After receiving the encoded packets, the client decodes the encoded packets to recover the original ones. The other clients also store the repeated chunks and the codes thereof The information of the Huffman codes of the repeated chunks needn&#39;t be transmitted every time for different clients since other clients may overhear the Huffman codes not intended to send to them.

Description:
[0001]    This application claims priority for Taiwan patent application no. 103139020 filed on Nov. 11, 2014, the content of which is incorporated by reference in its entirely. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a compression method for wireless communication in wireless networks, particularly to a compression method featuring dynamic coding for wireless communication in wireless networks. 
         [0004]    2. Description of the Related Art 
         [0005]    As the radio waves can penetrate through most barriers, the wireless communication technology is free of physical cables and exempt from maintaining the cable system. Therefore, the network industry has been persistently devoted to developing wireless communication technology. 
         [0006]    In the wireless network technology, data is divided into many segments and then sent out in a wireless broadcasting way in different frequencies, whereby different nodes can link mutually and exchange information. The wireless access point, also called the wireless transceiving box or the wireless network base station, is an intermediate device enabling interconnection among wireless network devices or interconnection between wireless network devices and wired network devices. 
         [0007]    In a wireless network, if a recipient detects an error in a packet sent by an access point, the recipient would demand the access point to transmit the packet once again. However, retransmission of packets would seriously decrease transmission speed in the wireless network. 
         [0008]    Besides, packet collision also greatly affects the efficiency of a wireless network. While the users directly communicate in a wireless network group, packet collision would cause the bandwidth to shrink obviously. If the bandwidth should reduce to lower than the minimum bandwidth required by the access points, the network communication would interrupt or break down, which would damage signals between nodes seriously. 
         [0009]    The present invention intends to solve the problem that the efficiency of wireless networks is reduced by packet retransmission and packet collision and thus proposes a compression method featuring dynamic coding for wireless communication in wireless networks. 
       SUMMARY OF THE INVENTION 
       [0010]    The primary objective of the present invention is to provide a compression method featuring dynamic coding for wireless communication in wireless networks, which determines whether a chunk has been encoded into a Huffman code and a hash function code according to the information of the repetition frequency of the chunk and transmits the chunk and the Huffman code thereof to all recipients of wireless networks, whereby to increase the repetition frequency of chunks, avoid retransmission and collision of packets, shorten the code length, and increase the overall compression rate. Further, the present invention uses a simple packet-division method, which is able to reduce computation load and easy to realize in the current network environment. 
         [0011]    Another objective of the present invention is to provide a compression method featuring dynamic coding for wireless communication in wireless networks, which uses the Huffman coding theory to undertake statistics of the data transmitted before to predict the probability of transmitting the same data in future and optimize the code length, and which uses a Huffman coding method that uses the shortest codes to replace the most frequently transmitted data obviously decrease the computation load of the recipients, whereby the recipients needn&#39;t empty the register for a long time and the repetition frequency increases. 
         [0012]    In order to achieve the abovementioned objectives, the present invention proposes a compression method featuring dynamic coding for wireless communication in wireless networks, which comprises steps: updating the information of the repetition frequencies of chunks and undertaking statistics of the repetition frequencies; determining whether the Huffman code of a chunk has been established and whether the chunk has a hash function code; determining whether the Huffman code of the chunk was transmitted before; then transmitting the hash function code or the chunks and the Huffman codes of the chunks. 
         [0013]    Below, embodiments are described in detail in cooperation with attached drawings to make easily understood the objectives, technical contents, characteristics and accomplishments of the present invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]      FIG. 1  schematically shows a wireless network transmission device according to one embodiment of the present invention; 
           [0015]      FIG. 2  schematically shows an access point according to one embodiment of the present invention; 
           [0016]      FIG. 3  shows a flowchart of a compression method featuring dynamic coding for wireless communication in wireless networks according to one embodiment of the present invention; 
           [0017]      FIG. 4  shows a flowchart of a compression method featuring dynamic coding having an additional process to check unrecorded chunks according to one embodiment of the present invention; 
           [0018]      FIG. 5  shows a flowchart of a compression method featuring dynamic coding, which is applied to clients, according to one embodiment of the present invention; 
           [0019]      FIG. 6  schematically shows the packet transmission in a wireless network according to one embodiment of the present invention; and 
           [0020]      FIG. 7  shows the repetition frequencies of the packets according to one embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0021]    The present invention mainly pertains to a compression method featuring dynamic coding for wireless communication in wireless networks. However, an embodiment of a related device will be used to fully demonstrate the technical thoughts of the present invention so as to enable the persons skilled in the art to understand, make, and use the present invention. 
         [0022]    Refer to  FIG. 1  and  FIG. 2 .  FIG. 1  schematically shows a wireless network transmission device according to one embodiment of the present invention.  FIG. 2  schematically shows an access point according to one embodiment of the present invention. The wireless network transmission-compression device  10  of the present invention comprises an access point  12  and clients  14  and  14 ′. The access point  12  is also called the wireless transceiving box or the wireless network base station. The clients  14  and  14 ′ are mobile devices, such as portable gamers, mobile phones, smartphones, tablet computers, and notebook computers. The access point  12  has a memory  16 , and the clients  14  and  14 ′ also respectively have memories  18  and  18 ′. 
         [0023]    The wireless network transmission-compression device  10  receives a packet  20  from the memory  16  of the access point  12 , divides the packet  20  into a plurality of chunks ABC, respectively establishes information of repetition frequencies and codes for the chunks ABC, and transmits the chunks ABC and the codes thereof to the clients  14  and  14 ′. Each of the clients  14  and  14 ′ receives the chunks ABC and the codes thereof and stores them in the memory  18  or  18 ′. In order to fully and clearly disclose the present invention to enable the persons skilled in the art to understand, make, and use the present invention, the transmitted data is simplified to be ABC, and the Huffman code representing each chunk is simplified to be 01, in  FIG. 1 . However, other codes can also be used to represent the chunks in the present invention. As shown in  FIG. 2 , the memory  16  of the access point  12  also records a new chunk ABC′ and the hash function (HF) code. Thereof in  FIG. 2 , #001 represents the hash function code. The 
         [0024]    Huffman code 01 and the hash function code #001 are stored in the memory  16  or the memories  18  and  18 ′. 
         [0025]    Refer to  FIG. 3 , and refer to  FIG. 1  again.  FIG. 3  shows a flowchart of a compression method featuring dynamic coding for wireless communication in wireless networks according to one embodiment of the present invention. The method of the present invention comprises Steps S 10 -S 22 . In Step S 10 , the method of the present invention divides a packet  20  into a plurality of chunks ABC which are to be used to transmit the chunks ABC to the clients  14  and  14 ′, and establishes information of repetition frequencies for the chunks ABC. In Step S 12 , the method of the present invention updates the information of the repetition frequencies of the chunks ABC and undertakes the statistics of the repetition frequencies. In Step S 14 , the method of the present invention determines whether the Huffman code 01 of one chunk ABC has been established. If the Huffman code 01 of the chunk ABC has been established, the process proceeds to 
         [0026]    Step S 142 . In Step S 142 , the method of the present invention updates the Huffman code 01 of the chunk ABC whose repetition frequency exceeds a preset frequency, and then the process proceeds to Step S 18 . If the Huffman code 01 of the chunk ABC has not yet been established, the process proceeds to Step S 144 . Step S 142  also can save the repetition frequency that exceeds a preset frequency, then after a time interval of a cycle, update the statistics information of repetition frequency of each chunk. If frequently update the statistics information of repetition frequency of each chunk, when the repetition frequency exceeds the preset frequency, it might increase the cost. And the Huffman code of chunk might have been updated without being used. In Step S 144 , the method of the present invention determines whether the repetition frequency of the chunk ABC satisfies the preset frequency, If yes, the process proceeds to Step S 142 , If no, the process proceeds to Step S 16 . 
         [0027]    In Step S 16 , the method of the present invention determines whether the chunk ABC has a hash function code #001. If the chunk ABC does not have a hash function code #001, the process proceeds to Step S 162 . In Step S 162 , the method of the present invention encoding each chunk ABC with a hash function code #001, stores the hash function code #001 in the memory  16 , and transmits a chunk ABC. If the chunk ABC has a hash function code #001, the process proceeds to Step S 164 . In Step S 164 , the method of the present invention transmitting a hash function code #001. 
         [0028]    As mentioned above, in Step S 142 , the method of the present invention updates the Huffman code 01 of the chunk ABC whose repetition frequency exceeds a preset frequency, and then the process proceeds to Step S 18 . In Step S 18 , the method of the present invention determines whether the Huffman code 01 of the chunk ABC was transmitted before. If the Huffman code 01 of the chunk ABC was transmitted before, the process proceeds to Step S 182 . In Step S 182 , the method of the present invention replaces the repeated chunk ABC with the Huffman code 01, and then the process proceeds to Step S 20 . In Step S 20 , the method of the present invention transmits the Huffman code 01. If the Huffman code 01 of the chunk ABC was not transmitted before, the process proceeds to Step S 184 . In Step S 184 , the method of the present invention assigns a Huffman code 01 to the chunk ABC that was not transmitted before, and then the process proceeds to Step S 22 . In Step S 22 , the method of the present invention transmits the chunk ABC and the Huffman code 01 thereof to the clients  14  and  14 ′ and stores the chunk ABC and the Huffman code 01 thereof in the memories  18  and  18 ′. In the present invention, the hash function code #001 used to encode the chunk ABC is a sequence of random numbers so as to compress the chunk ABC into a shorter sequence of bits. In the present invention, the update of a Huffman code is dependent on the time interval of a cycle with respect to the repetition frequency which is referred to the times of the appearance of the chunk ABC. The preset frequency is used as a threshold. Suppose that the preset frequency is 5. If the repetition frequency of a chunk ABC is smaller than 5, the method of the present invention does not assign a Huffman code to the chunk ABC. Refer to  FIG. 4 , and refer to  FIG. 2  again. The method of the present invention further comprises Step S 24  undertaken before Step S 12 . In Step S 24 , the method of the present invention determines whether the memory  16  has a chunk ABC that has not been stored yet. If the memory  16  has a chuck ABC that has not been stored yet, the process proceeds to Step S 242 . In Step S 242 , the method of the present invention defines the chunk ABC, which has not been stored yet, as a new chunk ABC′, and then the process proceeds to Step S 244 . In Step S 244 , the method of the present invention establishes the information of the repetition frequency of the new chunk ABC′. Then, the process proceeds to Step S 246 . In Step S 246 , the method of the present invention calculates the hash function code #001 of the new chunk ABC′. Then, the process proceeds to Step S 248 . In Step S 248 , the method of the present invention updates the new chunk ABC′ with the hash function code #001 and restores the new chunk ABC′ into the chunk ABC. If the memory  16  does not have a chuck ABC that has not been stored yet, the process proceeds to Step S 16 . 
         [0029]    Refer to  FIG. 5 , and refer to  FIG. 1  again.  FIG. 5  shows a flowchart of a compression method featuring dynamic coding for wireless communication in wireless networks, which is applied to clients, according to one embodiment of the present invention. The process of the method of the present invention applied to the clients  14  and  14 ′ succeeds to Step S 20  or Step S 22  and comprises Steps S 26 -S 32 . In Step S 26 , the method of the present invention receives and decomposes the chunk ABC. In Step S 28 , the method of the present invention determines whether the code corresponding to the chunk ABC is a Huffman code 01 or a hash function code #001. If the code corresponding to the chunk ABC is a Huffman code 01 or a hash function code #001, the process proceeds to Step S 30 . If the code corresponding to the chunk ABC is neither a Huffman code 01 nor a hash function code #001, the process proceeds to Step S 32 . In Step S 30 , the method of the present invention determines whether the Huffman code 01 or the hash function code #001 of the chunk ABC has existed. If the Huffman code 01 or the hash function code #001 of the chunk ABC has existed, the process proceeds to Step S 302 . In Step S 302 , the method of the present invention searches for the Huffman code 01 or the hash function code #001 corresponding to the chunk ABC, and restores the packet  20 . If the Huffman code 01 or the hash function code #001 of the chunk ABC does not exist, the process proceeds to Step S 304 . In Step S 304 , the method of the present invention asks for retransmitting the chunk ABC and the Huffman code 01 thereof In Step S 32 , the method of the present invention determining whether the chunk 
         [0030]    ABC transmitted with a corresponding Huffman code 01. If the chunk ABC transmitted with a corresponding Huffman code 01, the process proceeds to Step S 322 . In Step S 322 , the method of the present invention stores the chunks ABC and the Huffman codes thereof, and uses the chunks ABC to restore the packet  20 . If the chunk ABC not transmitted with a corresponding Huffman code 01, the process proceeds to Step S 324 . In Step S 324 , the method of the present invention producing the hash function code #001 of the corresponding chunk. 
         [0031]    In summary, the present invention proposes a compression method featuring dynamic coding for wireless communication in wireless networks, which includes technical thoughts: dividing the packet, which is to be sent to clients, into a plurality of chunks ABC all having a given length; undertaking statistics of the repetition frequency of each chunk ABC; establishing Huffman codes 01 for the sorted repetition frequencies, wherein the Huffman code 01 is dependent on the time interval of the cycle with respect to the repetition frequency; supposing that 01, 001, 0001 and 00001 respectively express the Huffman codes whose lengths increase in sequence; while a chunk ABC appears very frequently, using a shorter Huffman code 01; while a chunk ABC appears less frequently, using a longer Huffman code 00001. 
         [0032]    The present invention acquires higher transmission speed in a limited bandwidth in wireless transmission via increasing computation capacity and storage space in the access point  12  and the clients  14  and  14 ′. The present invention encodes chunks with the Huffman coding method and the hash-function coding method. Therefore, the present invention is applicable to mobile device networks and other wireless networks. 
         [0033]    The present invention records the behavior of packet transmission, encodes the packets according to the Huffman coding theory, and shares the Huffman codes in a wireless way. As the repeated packet is encoded with only few bits, the transmission speed and the bandwidth efficiency is significantly increased. As the wireless network has the characteristic of broadcasting, the access point  12  can share the codes of packets in a limited-resource transmission environment to enable the access points and mobile devices to achieve higher transmission throughput in a limited bandwidth. 
         [0034]    The present invention records the contents of the packets  20  transmitted before and the repetition frequencies of the contents, and then encodes the contents of the packets  20 . The content of the packet  20  having the highest repetition frequency is encoded with the shortest code. Thus, the total contents of the packet  20  have approximately optimized coding. The present invention modifies the coding tactics according to the history of the repetition frequencies of the contents of packets  20 . Therefore, the coding can adapt to the latest transmission condition of the wireless network. In the present invention, the computation for coding is mainly executed in the access point  12 . Therefore, the present invention is feasible for the clients  14  and  14 ′ having limited computation resources, such as mobile phones and tablet computers. 
         [0035]    The discussion made above and the related drawings have schematically demonstrated the device configuration and technical thoughts of the compression method featuring dynamic coding for wireless communication in wireless networks of the present invention. Below, the embodiments and the related statistic method of the present invention will be described in further detail in cooperation with Table. 1 and the related drawings. 
         [0000]    
       
         
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Trans- 
                   
                   
                   
                   
                   
                   
               
               
                 mission 
                 Con- 
                 Recip- 
                 Occur- 
                   
                 Coding 
                 Appearance for 
               
               
                 Order 
                 tent 
                 ient 
                 rence 
                 Code 
                 Method 
                 the First Time? 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1 
                 ABC 
                 14 
                 1 
                 #101 
                 HF 
                 yes 
               
               
                   
                   
                   
                   
                   
                   
                 (H(ABC) = #101) 
               
               
                 23 
                 DFE 
                     14′ 
                 1 
                 #001 
                 HF 
                 yes 
               
               
                   
                   
                   
                   
                   
                   
                 (H(DFE) = #001) 
               
               
                 56 
                 DFE 
                 14 
                 3 
                 #001 
                 generated 
                 no (generated) 
               
               
                 80 
                 DFE 
                 14 
                 7 
                 01 
                 Huffman 
                 no (01) 
               
               
                 100 
                 ABC 
                     14′ 
                 5 
                 00 
                 Huffman 
                 no (00) 
               
               
                   
               
             
          
         
       
     
         [0036]    Refer to  FIG. 6  and Table. 1.  FIG. 6  schematically shows the packet transmission in a wireless network according to one embodiment of the present invention. Suppose that the contents of the packet  20  are respectively “ABC” and “DEF. The access point  12  transmits the contents “ABC” and “DEF” to the clients  14  and  14 ′, and the contents are stored in the memories  18  and  18 ′. The method of the present invention establishes the Huffman code of the chunk ABC according to the repetition frequency thereof The higher the repetition frequency of a chunk ABC or DEF, the shorter the code the Huffman coding method uses to encode the chunk ABC or DEF, such as 00 and 01. The lower the repetition frequency of a chunk ABC or DEF, the longer the code the Huffman coding method uses to encode the chunk ABC or DEF. 
         [0037]    Refer to  FIG. 7 , and refer to  FIG. 1  again.  FIG. 7  shows the repetition frequencies of the packets according to one embodiment of the present invention, wherein the X coordinate represents the number of chunk and the Y coordinate represents the repetition frequency.  FIG. 7  records the transmission behavior of the access point  12  using the method of the present invention and transmitting one million chunk of packets and the performance thereof It is observed in  FIG. 7  that the overall repetition frequency of chunks is as high as over 60% for the access point using the method of the present invention. 
         [0038]    In conclusion, the present invention proposes a compression method featuring dynamic coding for wireless communication in wireless networks, which is characterized in dividing the packet into chunks and determining whether repeated chunks have been encoded before the packet is sent out; replacing the repeated chunks with corresponding codes, and transmitting the encoded chunks and the codes thereof; while transmitting the codes of repeated chunks to a specified client, also transmitting the same information to other clients within the coverage of transmission, whereby other mobile devices also receive the repeated chunks and the codes thereof and store the information; while transmitting the packet containing the repeated chunks, replacing the repeated chunks with the codes thereof 
         [0039]    Therefore, the method of the present invention divides a packet into chunks and determines whether the repeated chunks have been encoded before transmitting the packet. Then, the method of the present invention replaces the repeated chunks with the codes thereof If the code of the repeated chunk has never been sent out, the code is attached to the repeated chunk. Once the client receives a Huffman code, the Huffman code is used to decode the chunk and restore the encoded packet. While the codes of repeated chunks are transmitted to a specified client, the same information is also transmitted to the clients within the coverage of transmission. Then, the clients store the repeated chunks and the codes thereof In the present invention, it is unnecessary to transmit the codes to clients separately. While the statistic data of a repeated chunk is insufficient to establish the Huffman code thereof, the access point undertakes the hash operation and generates a hash code, which is to be used in encoding while transmitting the same chunk next time. 
         [0040]    The Huffman coding method used by the present invention not only can undertake statistics of the data transmitted before but also can use the statistic information to predict the probability of transmitting the data in the future, whereby can be acquired the most optimized code length. Further, the Huffman coding method greatly reduces the computation load of the clients. Thereby, the clients needn&#39;t empty the registers for a long time, and the repetition frequency is higher. The Huffman coding method used by the present invention can use the shortest code to replace the most common repeated chunk. 
         [0041]    After dividing a packet into a plurality of chunks in an access point, the method of the present invention establishes information of repetition frequencies for the chunks. Next, the method of the present invention determines whether the Huffman codes and the hash function codes of the chunks have been established. Next, the method of the present invention transmits the chunks and the Huffman codes thereof to all the clients of the wireless network. As the recipients are all the clients of the wireless network, the method of the present invention achieves a high repetition frequency of data. The Huffman coding method used by the present invention neither needs to retransmit the packet nor suffers from packet collision. Further, the Huffman coding method can shorten the length of codes and increase the overall compression rate. The method of the present invention has advantages of simple packet-division tactics and low computation load and is easy to realize in the current network environment. 
         [0042]    The present invention has been demonstrated with the embodiments above. However, these embodiments are only to exemplify the present invention but not to limit the scope of the present invention. Any equivalent modification or variation according to the spirit of the present invention is to be also included within the scope of the present invention, which is based on the claims stated below.